電話號碼的字母組合
題目來源：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
題目
給定一個僅包含數(shù)字 2-9 的字符串鲸湃，返回所有它能表示的字母組合盔腔。
給出數(shù)字到字母的映射如下（與電話按鍵相同）猎莲。注意 1 不對應任何字母谒兄。
圖源來自于 LeetCode
示例:
輸入："23"
輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
說明:
盡管上面的答案是按字典序排列的，但是你可以任意選擇答案輸出的順序。
解題思路
- 回溯（全排列組合，本題不涉及到剪枝）淹朋；
- 列出手機號碼對應的所有字母；
- 創(chuàng)建回溯函數(shù)
back_trace(combination, next_digits)列林，combination表示已組合的字母瑞你，以及下一步輸入的數(shù)字next_digits； - 若是沒有更多的數(shù)字希痴，根據(jù)限定條件者甲，將已經(jīng)組合完成的字母放到結果列表中；
- 若還有數(shù)字砌创，則遍歷后續(xù)數(shù)字所映射的字母虏缸，將字母組合。
- 當遞歸結束嫩实，返回結果列表刽辙。
- 時間復雜度：
，其中 N 表示數(shù)字對應 3 個字母的數(shù)量甲献，M 表示數(shù)字對應 4 個字母的數(shù)量宰缤。
代表輸入數(shù)字的長度。
- 空間復雜度：
個慨灭。
圖解
圖解
代碼實現(xiàn)
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# 手機號碼對應的字母
phone = {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']
}
# 回溯
def back_trace(combination, next_digits):
# 限定條件
# 確定組合
if len(next_digits) == 0:
res.append(combination)
else:
# 遍歷匹配數(shù)字的字母
for elem in phone[next_digits[0]]:
# 將字母組合起來
# 繼續(xù)下一個字母
back_trace(combination + elem, next_digits[1:])
res = []
if digits:
back_trace('', digits)
return res
實現(xiàn)結果
實現(xiàn)結果
以上就是使用回溯解決《電話號碼的字母組合》問題的主要內容。
歡迎關注微信公眾號《書所集錄》
