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"].

假設(shè) n個(gè)按鍵，每個(gè)按鍵的字母k個(gè)

Solution1：Backtracking(DFS)

回溯法，類(lèi)似深度優(yōu)先遍歷，如按鍵111，遍歷從aaa->aab...->ccc。實(shí)現(xiàn)上采用遞歸方式。

Solution1a：Backtracking(DFS)-a

思路：回溯(類(lèi)似DFS) cur_tmp_str使用不同的string(即占用不同的內(nèi)存: code中prefix + letters.charAt(i))，則不需要退后remove的步驟。
Time Complexity: Space Complexity:

Solution1b：Backtracking(DFS)-b

總結(jié)見(jiàn)：http://www.itdecent.cn/p/883fdda93a66
思路：回溯(類(lèi)似DFS) cur_tmp_str使用同一的string(占用相同的內(nèi)存)，通過(guò)StringBuilder實(shí)現(xiàn)，DFS到底 后通過(guò)remove后退。

Time Complexity: Space Complexity:

ab其實(shí)都是一樣的，就是先復(fù)制和后復(fù)制不同，如果先復(fù)制了就是過(guò)程中cur_str就是不同的，不需要remove來(lái)step back，后復(fù)制的話(huà) 之前因?yàn)橥籹tr，則需要remove 來(lái)step back，但最終時(shí)間復(fù)雜度都是一樣的,都是k^n?，因?yàn)樽詈罂隙ǘ家獜?fù)制到result. 但空間復(fù)雜度不同，"先復(fù)制"產(chǎn)生了logn層str變量O(k)?

Solution2：類(lèi)似廣度優(yōu)先方式

a b c
aa ba ca ab bb cb ac bc cc
[aa ba ca ab bb cb ac bc cc]a [aa ba ca ab bb cb ac bc cc]b [aa ba ca ab bb cb ac bc cc]c

Solution2a："BFS"-a

思路：類(lèi)似BFS方式，遍歷原數(shù)組 分別在原基礎(chǔ)結(jié)果上 分別再加新一位按鍵的letters.
Time Complexity: Space Complexity:

Solution2b："BFS"-b

思路：類(lèi)似BFS方式，like queue 分別在原基礎(chǔ)結(jié)果上 分別再加新一位按鍵的letters
Time Complexity: Space Complexity:

Solution1a Code：

class Solution1a {
    private static final String[] KEYS = {""/*0*/, ""/*1*/, "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        List<String> result = new LinkedList<String>();
        if (digits == null || digits.length() == 0) return result;
        combination("", digits, 0, result);
        return result;
    }

    private void combination(String prefix, String digits, int cur_index, List<String> result) {
        // add to the result
        if (cur_index == digits.length()) {
            result.add(prefix);
            return;
        }

        String letters = KEYS[digits.charAt(cur_index) - '0'];
        for (int i = 0; i < letters.length(); i++) {
            String new_prefix = prefix + letters.charAt(i);
            combination(new_prefix, digits, cur_index + 1, result);

        }
    }
}

Solution1b Code：

class Solution {
    private static final String[] KEYS = { ""/*0*/, ""/*1*/, "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    public List<String> letterCombinations(String digits) { 
        List<String> result = new LinkedList<String>();
        if(digits == null || digits.length() == 0)  return result;
        
        StringBuffer cur_res = new StringBuffer();
        combination(digits, 0, cur_res, result);
        return result;
    }
    private void combination(String digits, int start, StringBuffer cur_res, List<String> result) {
        // add to the result
        if(start == digits.length()) {
            result.add(cur_res.toString());
            return;
        }

        String letters = KEYS[digits.charAt(start) - '0'];
        for(int i = 0; i < letters.length(); i++) {
            cur_res.append(letters.charAt(i));
            combination(digits, start + 1, cur_res, result);
            cur_res.deleteCharAt(cur_res.length() - 1);

        }
    }
}

Solution2a Code：

class Solution2a {
    private static final String[] KEYS = {""/*0*/, ""/*1*/, "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) { 
        List<String> result = new LinkedList<String>();
        if(digits == null || digits.length() == 0)  return result;
        
        result.add("");
        for (int i = 0; i < digits.length(); i++) {
            String letters = KEYS[digits.charAt(i) - '0'];
            LinkedList<String> cur_results = new LinkedList<String>();
            for (int c = 0; c < letters.length(); c++) {
                for (String ret : result) {
                    cur_results.add(ret + letters.charAt(c));
                }
            }
            result = cur_results;
        }
        return result;
    }
}

Solution2b Code：

class Solution2b {
    private static final String[] KEYS = {""/*0*/, ""/*1*/, "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) { 
        LinkedList<String> result = new LinkedList<String>();
        if(digits == null || digits.length() == 0)  return result;
        
        result.add("");
        for (int i = 0; i < digits.length(); i++) {
            String letters = KEYS[digits.charAt(i) - '0'];
            while(result.peek().length() == i) {
                String last_level_str = result.remove();
                for(int c = 0; c < letters.length(); c++) {
                    result.add(last_level_str + letters.charAt(c));
                }
            }
        }
        return result;
    }
}