总结

该网页主要介绍了如何通过LeetCode学习深度优先搜索（DFS）和回溯算法，并提供了零元挑战赛的活动信息，以及进階篇课程的预购和相关优惠。

摘要

网页标题为《从LeetCode学演算法 - 111 DFS (18) / Backtracking (8)》，是一篇关于演算法学习的文章。文章开头提到了零元挑战赛的活动，要求参与者在修完课程后三个月内找到新工作并撰写心得，方能获得全额退费的机会。此外，还有一个抽奖活动，要求在Python Taiwan的特定帖子下公开分享，点赞并留言，满足条件的参与者可能获得免费的《从LeetCode学演算法｜进階篇》和《从LeetCode学演算法｜面试篇》课程。

文章还介绍了《从LeetCode学演算法｜进階篇》的预购信息，提到这一版选用了40道难度增强的LeetCode题目，并附赠面试篇课程，内容包括面试准备须知和不同经验的工程师訪談分享。文章还提供了题目“0784. Letter Case Permutation”的详细解析，包括如何使用DFS和回溯算法生成所有可能的字符串变化。最后，文章提供了Python和Java的示例代码，并讨论了时间和空间复杂度，以及相似问题和延伸学习的建议。

观点

网页内容的主要观点包括：

LeetCode是学习演算法的有效平台：文章通过具体的题目“0784. Letter Case Permutation”展示了如何利用LeetCode平台学习DFS和回溯算法。
零元挑战赛激励学习：通过提供退费机制和抽奖活动，鼓励学习者积极参与课程学习并实际应用所学知识。
进階课程的价值：强调进階篇课程的重要性，它包含了更深入的LeetCode题目和面试准备的实用信息，适合各种职业发展阶段的工程师。
回溯算法的核心概念：文章解释了回溯算法的基本概念，即在搜索过程中遇到死胡同时回溯到上一个节点，并恢复之前的状态。
编程实践与分享：提供了具体的Python和Java代码示例，帮助读者理解如何将回溯算法应用于解决实际问题，并鼓励读者提供反馈和建议以帮助改进内容。
面试准备的重要性：文章指出面试篇课程的重要性，它不仅包括面试技巧分享，还有国内外工程师的訪談经验，对于求职者来说是一份宝贵的资源。

從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

請幫我隨手點開下面的SHOW EMBED並按5個like～喜歡的話也可以幫我拍拍手～ (按讚不用錢，感謝支持寫作~)

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:

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

Example 2:

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

Example 3:

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

Example 4:

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種。

那麼，我們怎麼樣處理這樣子的產生的過程呢？這就要回頭複習一下回溯法的概念了！以前我們提到過，回溯法就是當走到一段，無法再往下走時，回到上一步並還原前面的痕跡，再往下一條路走的做法。因此，我們來看待這題會變成這樣： 1. 先將整個字串轉成小寫(要都轉成大寫也可以) 2. 從index 0開始往下走(將現在的位置定為pos)，當順著往下走都不改變時，最後應該會走到底部，此時pos == 整個字串長，這會是其中一個字串變化，可記錄到結果(res)中。 3. 接著，回到上一步時，我們可以檢查pos位置是否為字母， 是的話，我們可以改成將該位置的字母轉為大寫，再重新往下走一次(因為這樣子變化又不一樣了) 4. 走到底回到上一層時，再將字母轉回小寫(回溯法的復原) 5. 最終，全數走完時，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

如果你／妳覺得這篇文章不錯，請拍手並給5個Like。(點開SHOW EMBED!)
也請記得「Follow」我，隨時收看最新的文章。