17. Letter Combinations of a Phone Number (Medium) Facebook Google Amazon Uber Dropbox

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input: Digit string "23"

Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution 1: DFS O(n * 4^n); O(n)

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

        dfs(res, new StringBuilder(), digits, 0);
        return res;
    }

    /**
     * Generate combinations according to each digit.
     * Get current position's possible letters and then append to the combination so far.
     * Pass the generated combination to the next call.
     * When all digits are used, add combination to the result collection.
     */
    private void dfs(List<String> res, StringBuilder sb, String digits, int start) {
        if (sb.length() == digits.length()) {
            res.add(sb.toString());
            // return;
        }

        int len = sb.length();
        String[] letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        char[] letter = letters[digits.charAt(start) - '0'].toCharArray();
        for (char c : letter) {
            dfs(res, sb.append(c), digits, start + 1);
            sb.setLength(len); //backtrack
        }
    }

Solution 2: BFS O(n * 4^n); O(n)

    /**
     * BFS.
     * Build combination level by level.
     * The length of the combination is the same as the level.
     * Add all possible letters to each of the result in previous level.
     */    
    public List<String> letterCombinationsB(String digits) {
        if (digits == null || digits.length() == 0) {
            return Collections.emptyList();
        }

        String[] letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        LinkedList<String> queue = new LinkedList<>();
        queue.offer("");
        for (int i = 0; i < digits.length(); i++) { //O(n)
            char[] letter = letters[digits.charAt(i) - '0'].toCharArray();
            while (queue.peek().length() == i) { //O(n^4)
                String s = queue.poll();
                for (char c : letter) {
                    queue.offer(s + c);
                }
            }
        }
        return queue;
    }

Follow Up:

1. 面试官上来让递归，写完后面试官说要打印不要返回，于是马上改。改完后问时间空间复杂度。问空间上能否优化。
2. 变形，变成用这些组合测密码，有个回传密码是否正确的函数可用，问正确的密码。
3. 第一个 follow up：如果今天给你一本字典，裡面有【几千万个单字】，你可以用任何数据结构储存这个字典， 请问你怎麽从你的 letter combination 中找出 meaningful word? 举个例子，三个数字可能可以组成 “aaa”, “abc”, “dog"， 那我们就只留下 “dog” ，因为只有 “dog” 是一个单词，楼主一开始提议用 set 储存，但是他说太 expensive ，后来改成用 trie ， 然后找 prefix ，如果确定没有这个 prefix 就可以直接 pruning 了，面试官感觉很满意
4. 第二个 follow up：如果今天不只要你找出一个单词的组成，连两个单词的组合都要找出来呢？ 比方说七个字的组成可以有 “element”(一个单词)，但也会有 “eatrice”(eat rice，两个单词) 这样的组成，能不能把这个也找出来呢？但问到这裡的时候时间已经剩很少，没什麽太多时间讨论，我一开始先提出可以用 word break 的想法判断是不是两个字典中的单词，但面试官说其实方法很简单，就是把 trie 的 tail 跟 root 相连，这样找完一个字之后就会接着回头找其他的字，结果也就会包含多个字的组合了，然后我提出了一些这个方法的好跟不好的地方，面试官也觉得不错，皆大欢喜之下结束．