LeetCode 17. 電話號(hào)碼的字母組合是一道經(jīng)典的回溯/笛卡爾積問題。核心思路是遍歷每個(gè)數(shù)字對(duì)應(yīng)的字母逐層組合。核心思路建立數(shù)字到字母的映射表手機(jī)九宮格對(duì)每個(gè)數(shù)字取出其對(duì)應(yīng)的所有字母用迭代或回溯生成所有組合Python3 完整實(shí)現(xiàn)解法一迭代法推薦最直觀class Solution:def letterCombinations(self, digits: str) - list[str]:if not digits:return []phone { 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz, } result [] for digit in digits: result [prev ch for prev in result for ch in phone[digit]] return result解法二回溯法class Solution:def letterCombinations(self, digits: str) - list[str]:if not digits:return []phone { 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz, } result [] def backtrack(index, path): if index len(digits): result.append(path) return for ch in phone[digits[index]]: backtrack(index 1, path ch) backtrack(0, ) return result解法三itertools.product最簡(jiǎn)潔from itertools import productclass Solution:def letterCombinations(self, digits: str) - list[str]:if not digits:return []phone { 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz, } letters [phone[d] for d in digits] return [.join(combo) for combo in product(*letters)]三種解法對(duì)比項(xiàng)目 迭代法 回溯法 itertools時(shí)間復(fù)雜度 O(4? · n) O(4? · n) O(4? · n)空間復(fù)雜度 O(4?) O(n) 遞歸棧 O(4?)可讀性 ??? ??? ??? 最簡(jiǎn)潔面試推薦 ? 好講思路 ? 通用模板 ? 依賴庫(kù)函數(shù)其中 n 為 digits 長(zhǎng)度4 是因?yàn)閿?shù)字 7、9 各有 4 個(gè)字母是最壞情況。關(guān)鍵細(xì)節(jié)空輸入直接返回 []題目要求輸入為空時(shí)返回空列表不是 [“”]迭代法的核心每處理一個(gè)新數(shù)字就把已有組合與新數(shù)字的每個(gè)字母做笛卡爾積用列表推導(dǎo)式一行搞定回溯法的關(guān)鍵index 表示當(dāng)前處理到第幾個(gè)數(shù)字path 是當(dāng)前已拼好的字符串到達(dá)末尾時(shí)收集結(jié)果product(letters)解包將列表展開為多個(gè)參數(shù)product(“abc”, “def”) 等價(jià)于求兩個(gè)集合的笛卡爾積面試中迭代法最好講清楚思路回溯法是最通用的模板適合擴(kuò)展到更復(fù)雜的組合問題。這道題的逆題——給定字符串判斷是否為有效羅馬數(shù)字LeetCode 38要不要也用 Python 寫一遍