mq049.电话号码的字母组合

回溯法，自己写了一下非常慢，然后就看了一下题解，和之前的“全排列”那个题的解法几乎一样。这个算法的时间复杂度是O（N），空间复杂度是O（N）。

python:

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

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

        def backtrack(x):
            if x == len(digits):
                res.append("".join(combination))
            else:
                digit = digits[x]
                for c in d[digit]:
                    combination.append(c)
                    backtrack(x+1)
                    combination.pop()
    
        res = []
        combination = []
        backtrack(0)
        return res

PREVIOUSlc017.电话号码的字母组合

NEXTlc022.括号生成