LeetCode 17. 電話號碼的字母組合是一道經(jīng)典的回溯/笛卡爾積問題。核心思路是遍歷每個數(shù)字對應的字母逐層組合。核心思路建立數(shù)字到字母的映射表手機九宮格對每個數(shù)字取出其對應的所有字母用迭代或回溯生成所有組合Python3 完整實現(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最簡潔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)]三種解法對比項目 迭代法 回溯法 itertools時間復雜度 O(4? · n) O(4? · n) O(4? · n)空間復雜度 O(4?) O(n) 遞歸棧 O(4?)可讀性 ??? ??? ??? 最簡潔面試推薦 ? 好講思路 ? 通用模板 ? 依賴庫函數(shù)其中 n 為 digits 長度4 是因為數(shù)字 7、9 各有 4 個字母是最壞情況。關(guān)鍵細節(jié)空輸入直接返回 []題目要求輸入為空時返回空列表不是 [“”]迭代法的核心每處理一個新數(shù)字就把已有組合與新數(shù)字的每個字母做笛卡爾積用列表推導式一行搞定回溯法的關(guān)鍵index 表示當前處理到第幾個數(shù)字path 是當前已拼好的字符串到達末尾時收集結(jié)果product(letters)解包將列表展開為多個參數(shù)product(“abc”, “def”) 等價于求兩個集合的笛卡爾積面試中迭代法最好講清楚思路回溯法是最通用的模板適合擴展到更復雜的組合問題。這道題的逆題——給定字符串判斷是否為有效羅馬數(shù)字LeetCode 38要不要也用 Python 寫一遍