分析

• 本题的考点：递归回溯。

• 首先将每个数字对应的字母存入一个数组中，然后直接暴搜出所有方案即可。

代码

• C++

class Solution {
public:
    vector<string> ans;  // 存储答案
    string strs[10] = {
        "", "", "abc", "def",
        "ghi", "jkl", "mno",
        "pqrs", "tuv", "wxyz",
    };

    vector<string> letterCombinations(string digits) {

        if (digits.empty()) return ans;
        dfs(digits, 0, "");
        return ans;
    }

    // 当前遍历到digits[u], 结果存储在path中
    void dfs(string digits, int u, string path) {
        if (u == digits.size()) ans.push_back(path);
        else {
            for (auto c : strs[digits[u] - '0'])
                dfs(digits, u + 1, path + c);
        }
    }
};

• Java

class Solution {
    List<String> ans = new ArrayList<>();
    String[] strs = {
        "", "", "abc", "def",
        "ghi", "jkl", "mno",
        "pqrs", "tuv", "wxyz",
    };

    public List<String> letterCombinations(String digits) {

        char[] s = digits.toCharArray();

        if (s.length == 0) return ans;
        dfs(s, 0, "");
        return ans;
    }

    // 当前遍历到digits[u], 结果存储在path中
    private void dfs(char[] s, int u, String path) {
        if (u == s.length) ans.add(path);
        else {
            for (char c : strs[s[u] - '0'].toCharArray())
                dfs(s, u + 1, path + c);
        }
    }
}

时空复杂度分析

• 时间复杂度：指数级别的。

• 空间复杂度：和递归深度有关，$O(n)$，n为digit长度。