17. 电话号码的字母组合

思路

这题我一开始使用的是BFS的思想，如下面的第一个代码所示。然而这样做存在不足，因为需要频繁构建StringBuilder来存储当前层的字符串。

对于字符串的频繁操作，如果使用DFS+回溯的思想，就可以减少这个反复创建的开销，效率更高。因为这个时候我们已经预先定好了将要插入字符的长度，并且可以重复利用之前的子字符串，只需要在到达叶子节点时把答案加入答案数组即可。

Code

class Solution {
    Queue<StringBuilder> ans = new LinkedList<>();
    private static final char[][] MAP = {
        {}, {}, {'a','b','c'}, {'d','e','f'}, {'g','h','i'}, 
        {'j','k','l'}, {'m','n','o'}, {'p','q','r','s'}, 
        {'t','u','v'}, {'w','x','y','z'}
    };
    public List<String> letterCombinations(String digits) {
        List<String> ret = new ArrayList<>();
        if (digits.isEmpty()) return ret;
        ans.offer(new StringBuilder());
        for (int i = 0; i < digits.length(); i++) {
            bfs(digits.charAt(i) - '0');
        }
        while (!ans.isEmpty()) {
            ret.add(ans.poll().toString());
        }
        return ret;
    }

    public void bfs(int num) {
        int m = ans.size();
        for (int i = 0; i < m; i++) {
            StringBuilder sb = ans.poll();
            for (int j = 0; j < MAP[num].length; j++) {
                StringBuilder temp = new StringBuilder(sb);
                ans.offer(temp.append(MAP[num][j]));
            }
        }
    }
}

class Solution {
    private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    private final List<String> ans = new ArrayList<>();
    private char[] digits;
    private char[] path;

    public List<String> letterCombinations(String digits) {
        int n = digits.length();
        if (n == 0) {
            return List.of();
        }
        this.digits = digits.toCharArray();
        path = new char[n]; // 注意 path 长度一开始就是 n，不是空数组
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == digits.length) {
            ans.add(new String(path));
            return;
        }
        for (char c : MAPPING[digits[i] - '0'].toCharArray()) {
            path[i] = c; // 直接覆盖
            dfs(i + 1);
        }
    }
}