(FB) Phone Letter Combination

Phone Letter Combination

把这题单独拿出来，是因为这是个非常典型的递归 / 迭代都很直观的搜索类问题，一个 DFS，一个 BFS.

BFS 就靠 Queue，以 queue 首长度 == i 来判断层数，反复做 join. 另外维护一个 String[] 用作字典查询。

    public List<String> letterCombinations(String digits) {
        LinkedList<String> queue = new LinkedList<String>();
        if(digits == null || digits.length() == 0) return queue;

        queue.add("");
        String[] letters = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        for(int i = 0; i < digits.length(); i++){
            int cur = digits.charAt(i) - '0';
            while(queue.peek().length() == i){
                String str = queue.remove();
                char[] candidates = letters[cur].toCharArray();
                for(char chr : candidates){
                    queue.add(str + chr);
                }
            }
        }

        return queue;
    }

DFS 写法就是做了无数次的 backtracking 写法。本质上，都是殊途同归的状态空间搜索罢了。

    public List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<String>();
        if(digits == null || digits.length() == 0) return list;
        String[] letters = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        dfs(list, new StringBuilder(), digits, letters, 0);

        return list;
    }

    private void dfs(List<String> list, StringBuilder sb, String digits, String[] letters, int pos){
        if(sb.length() == digits.length()){
            list.add(sb.toString());
            return;
        }

        for(int i = pos; i < digits.length(); i++){
            String str = letters[digits.charAt(i) - '0'];
            for(int j = 0; j < str.length(); j++){
                int length = sb.length();
                sb.append(str.charAt(j));
                dfs(list, sb, digits, letters, i + 1);
                sb.setLength(length);
            }
        }
    }