电话号码的字母组合

视频讲解

答疑

问：为什么视频中在介绍 $dfs (i)$ 的含义时，说我们在枚举下标 $\geq i$ 的剩余部分？ $dfs (i)$ 不是在枚举 $i$ 吗？

答： $dfs (i)$ 处理的是从下标 $i$ 到末尾的所有字母组合。 $dfs (i)$ 不仅仅在枚举 $i$ ，还包含了 $dfs (i + 1), dfs (i + 2), \dots, dfs (n)$ 这之后的所有递归调用。单纯说「枚举 $i$ 」是不准确的，因为除了枚举 $i$ ，还要递归处理剩余部分。正因为如此，我视频中讲的是 $\geq i$ 而不是等于 $i$ 。

Python 解法1C++ 解法1

python

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

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        n = len(digits)
        if n == 0:
            return []
  
        ans = []
        path = [''] * n  # 注意 path 长度一开始就是 n，不是空列表

        def dfs(i: int) -> None:
            if i == n:
                ans.append(''.join(path))
                return
            for c in MAPPING[int(digits[i])]:
                path[i] = c  # 直接覆盖
                dfs(i + 1)

        dfs(0)
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
    static constexpr string MAPPING[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public:
    vector<string> letterCombinations(string digits) {
        int n = digits.length();
        if (n == 0) {
            return {};
        }

        vector<string> ans;
        string path(n, 0); // 注意 path 长度一开始就是 n，不是空串

        // lambda 递归
        auto dfs = [&](this auto&& dfs, int i) -> void {
            if (i == n) {
                ans.emplace_back(path);
                return;
            }
            for (char c : MAPPING[digits[i] - '0']) {
                path[i] = c; // 直接覆盖
                dfs(i + 1);
            }
        };

        dfs(0);
        return ans;
    }
};

复杂度分析

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

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

视频讲解 ​

答疑 ​

复杂度分析 ​

分类题单 ​

视频讲解

答疑

复杂度分析

分类题单