從LeetCode學演算法 - 111 DFS (18) / Backtracking (8)

0784. Letter Case Permutation (Medium)

寫在前面

目前0元挑戰賽 的活動已經開始囉！
只要修課後三個月內完課且成功錄取新工作並撰寫心得，
課程就會全額退費喲！請使用下面連結看更詳細的規則說明：

零元求職挑戰賽 Python 組｜從 LeetCode 學演算法 + 面試成功指南 http://bit.ly/zeroclg

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/leetcodeadv

Question

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. You can return the output in any order .

Example 1

1
2
Input: S = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

Example 2

1
2
Input: S = "3z4"
Output: ["3z4","3Z4"]

Example 3

1
2
Input: S = "12345"
Output: ["12345"]

Example 4

1
2
Input: S = "0"
Output: ["0"]

Constraints

S will be a string with length between 1 and 12.
S will consist only of letters or digits.

分析/解題

給定一個字串S，
我們可以任意將其中的單一字母轉換成小寫或大寫，
以創造出另一個字串。
回傳一個列表，當中包含所有我們可以創造出來的字串。
(回傳的字串順序可以不同)
(限制：S的長度會在1~12之間，且S只會有字母或數字)

這個題目實際上並不是很難想，
從直觀上來說，就是找出所有字母的地方(因為只有字母可以變)，
讓它是小寫或大寫這兩種可能，會產生不一樣的字串，
因此如果當中存在L個字母的話，
其變化就會有2^L種。

那麼，我們怎麼樣處理這樣子的產生的過程呢？
這就要回頭複習一下回溯法的概念了！
以前我們提到過，回溯法就是當走到一段，無法再往下走時，
回到上一步並還原前面的痕跡，再往下一條路走的做法。
因此，我們來看待這題會變成這樣：

先將整個字串轉成小寫 (要都轉成大寫也可以)
從index 0 開始往下走(將現在的位置定為pos )，
當順著往下走都不改變 時，
最後應該會走到底部，此時pos == 整個字串長 ，
這會是其中一個字串變化，可記錄到結果(res)中 。
接著，回到上一步時，
我們可以檢查pos位置是否為字母 ，
是的話 ，我們可以改成將該位置的字母轉為大寫 ，
再重新往下走一次(因為這樣子變化又不一樣了)
走到底回到上一層時，再將字母轉回小寫(回溯法的復原)
最終，全數走完時，res 即會紀錄所有的答案。

所以在使用DFS和回溯法時，
讀者請切記兩個要點：
1. 走到死路(結束時該回頭)的條件要設定好
2. 被更改的東西，在這條路線結束後，記得復原

依此，寫成程式碼如下：

Java

Java的部分，使用toLowerCase()和toCharArray()，
將字串轉換成全小寫 的字元陣列，方便修改；
我們用helper函數來進行DFS+Backtracking。
在轉換上，使用new String(a)可以從一個字元陣列生成一個字串。
可能

Python

Python的部分，使用list() 來拆成串列，
同時組成字串是使用**’’.join()** 來處理的，
檢查字母是使用isalpha() 函式；
同時請留意**.upper()和.lower()並不直接對原來的東西做修改** ，
而是會回傳新的str ，所以請將其輸入回a[pos]裡，
才會真正修改到。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(2^L)/O(len(S)), L為字串中字母的數量)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

想看看其他題目嗎？
歡迎從第零篇 找你想要的！

同時追蹤粉專以獲得更多新文章的通知：
跟著Desolve學程式

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve