今天是紀錄LeetCode解題的第十七天

第十七題題目：Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

給定一個字串包含數字2~9，回傳數字所對應的字母的所有組合，回傳的答案可以是任何順序
以下是數字所對應到的字母(就像電話按鈕一樣)，注意1沒有任何對應的字母

解題思路

我們先遍歷他給的digits，把要組合的字母存進data裡，接著用回溯法把所有可能的組合排列出來，假設'abc'和'def'做組合，找到'ad'組合後，回溯'd'，再用'a'去找下一個可以做組合的字母'e'，找到'ae'，再回溯，用'a'作配對，找到'f'，組合成'af'，接著都沒有可以配對的字母了，那麼回溯'a'，換找'b'，依此類推來找到所有組合

程式碼

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dic = {"1":"","2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
        if not digits:
            return []
        else:
            data = []
            for c in digits:
                data.append(dic[c])
            result = []
            dfs(0,[],data,result)
            return result
def dfs(index,path,data,result):
    if index == len(data):
        result.append("".join(path))
        return
    for c in data[index]:
        dfs(index+1,path+[c],data,result)

執行過程

初始狀態

• digits = '23'
• data = ['abc','def']
• result = []

第一次執行(找和a的所有組合)

• index = 0
• path = []
• for c in data[index] → for c in data['abc'] → c = 'a'
• dfs(index+1,path+[c],data,result) → dfs(1,path+['a'],data,result)

• index = 1
• path = ['a']
• for c in data[index] → for c in data['def'] → c = 'd'
• dfs(index+1,path+[c],data,result) → dfs(2,path+['d'],data,result)

• index = 2
• path = ['a','d']
• if index == len(data) → result.append("".join(path)) → result = ['ad'] → return回到上一個步驟

• index = 1
• path = ['a']
• for c in data[index] → for c in data['def'] → c = 'e'
• dfs(index+1,path+[c],data,result) → dfs(2,path+['e'],data,result)

• index = 2
• path = ['a','e']
• if index == len(data) → result.append("".join(path)) → result = ['ad','ae'] → return回到上一個步驟

依此類推找到所有的組合，這題也是用到了DFS+Backtracking的概念，是很經典的字母組合題型，如果還不熟悉此演算法的，可以多從這樣的簡單題實作累積解題經驗