Letter Combinations of a phone number

DFS

• 对于sb的回溯，要在加入sb之前提前取length，用setLength()
• sb不需要担心深拷贝问题

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> results = new ArrayList<>();
        if (digits == null || digits.length() == 0) return results;

        String[] dict = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        dfs(digits, 0, results, new StringBuilder(), dict);
        return results;
    }

    public void dfs(String digits, int pos, List<String> results, StringBuilder path, String[] dict) {
        if (path.length() == digits.length()) {
            results.add(path.toString());
            return;
        }

        for (int i = pos; i < digits.length(); i++) {
            char num = digits.charAt(i);
            String str = dict[num - '0'];

            for (int j = 0; j < str.length(); j++) {
                int length = path.length();
                path.append(str.charAt(j));
                dfs(digits, i+1, results, path, dict);
                path.setLength(length);
            }

        }
    }
}

BFS