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

假设 n个按键，每个按键的字母k个

Solution1：Backtracking(DFS)

回溯法，类似深度优先遍历，如按键111，遍历从aaa->aab...->ccc。实现上采用递归方式。

Solution1a：Backtracking(DFS)-a

思路：回溯(类似DFS) cur_tmp_str使用不同的string(即占用不同的内存: code中prefix + letters.charAt(i))，则不需要退后remove的步骤。
Time Complexity: Space Complexity:

Solution1b：Backtracking(DFS)-b

总结见：http://www.jianshu.com/p/883fdda93a66
思路：回溯(类似DFS) cur_tmp_str使用同一的string(占用相同的内存)，通过StringBuilder实现，DFS到底 后通过remove后退。

Time Complexity: Space Complexity:

ab其实都是一样的，就是先复制和后复制不同，如果先复制了就是过程中cur_str就是不同的，不需要remove来step back，后复制的话 之前因为同一str，则需要remove 来step back，但最终时间复杂度都是一样的,都是k^n?，因为最后肯定都要复制到result. 但空间复杂度不同，"先复制"产生了logn层str变量O(k)?

Solution2：类似广度优先方式

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

思路：类似BFS方式，遍历原数组 分别在原基础结果上 分别再加新一位按键的letters.
Time Complexity: Space Complexity:

Solution2b："BFS"-b

思路：类似BFS方式，like queue 分别在原基础结果上 分别再加新一位按键的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;
    }
}