[leetcode/lintcode 題解]大廠面試真題詳解： 電話号碼的字母組合

描述

給一個不包含0和1的數字字元串，每個數字代表一個字母，請傳回其所有可能的字母組合。

下圖的手機按鍵圖，就表示了每個數字可以代表的字母。

td {white-space:pre-wrap;border:1px solid #dee0e3;}12ABC3DEF4GHI5JKL6MNO7PQRS8TUV9WXYZ

以上的答案是按照詞典編撰順序進行輸出的，不過，在做本題時，你也可以任意選擇你喜歡的輸出順序。

線上評測位址：

領扣題庫官網

樣例 1:
輸入: "23"
輸出: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
解釋: 
'2' 可以是 'a', 'b' 或 'c'
'3' 可以是 'd', 'e' 或 'f'           

樣例 2:
輸入: "5"
輸出: ["j", "k", "l"]           

解題思路

使用深度優先搜尋算法。

源代碼

KEYBOARD = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
}           

class Solution:

@param digits: A digital string
    @return: all posible letter combinations
    """
    def letterCombinations(self, digits):
        if not digits:
            return []
            
        results = []
        self.dfs(digits, 0, [], results)
        
        return results
    
    def dfs(self, digits, index, chars, results):
        if index == len(digits):
            results.append(''.join(chars))
            return
        
        for letter in KEYBOARD[digits[index]]:
            chars.append(letter)
            self.dfs(digits, index + 1, chars, results)
            chars.pop()           

更多題解參考：

九章官網solution