17.Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

Solution:

python

MAPPING = "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        n = len(digits)
        path = [''] * n # 注意 path 长度一开始就是 n，不是空列表
        ans = []
        def dfs(i):
            if i == n: # 不是 n-1
                ans.append(''.join(path))
                return
            for c in MAPPING[int(digits[i])]:
                path[i] = c # 直接覆盖，不用恢复现场
                dfs(i + 1)
        dfs(0)
        return ans

复杂度分析

时间复杂度：O(n4^n)，其中 n 为 digits 的长度。最坏情况下每次需要枚举 4 个字母，递归次数为一个满四叉树的节点个数，那么一共会递归 O(4^n) 次（等比数列和），再算上加入答案时复制 path 需要 O(n) 的时间，所以时间复杂度为 O(n4^n)。
空间复杂度：O(n)。返回值的空间不计。