Letter Combinations of a Phone Number

Solution

Backtracking

写清楚边界条件和非边界条件 回溯三问：

• 当前操作：枚举 path[i] 要填入的字母
• 子问题：构造字符串 >= i 的部分
• 下一个子问题：构造字符串 >= i+1 的部分

dfs(i) --> dfs(i+1)

def letterCombinations(self, digits: str) -> List[str]:
    if not digits:
        return []

    dct = {
        2: "abc",
        3: "def",
        4: "ghi",
        5: "jkl",
        6: "mno",
        7: "pqrs",
        8: "tuv",
        9: "wxyz"
    }
    res = []
    n = len(digits)
    # path = ['' for _ in range(n)]
    path = []

    def backtracking(i):
        if i == n:
            res.append(''.join(path[:]))
            return
        num = int(digits[i])
        for letter in dct[num]:
            path.append(letter)
            backtracking(i+1)
            path.pop()
        return

    backtracking(0)
    return res