Amazon-Letter Combinations of a

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

Input: "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:

    final String[] layout={
        " ",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    
    public List<String> letterCombinations(String digits) {
        List<String> res=new ArrayList<>();
        if(digits==null||digits.length()==0||!digits.matches("[2-9]+")) return res;
        
        char[] cdigits=digits.toCharArray();
        
        StringBuilder tmp=new StringBuilder();
        find(cdigits,0,res,tmp);
        
        return res;
    }
    private void find(char[] digits,int index,List<String> res,StringBuilder tmp){
        if(index==digits.length){
            res.add(tmp.toString());
            return;
        }
        
        String letters=layout[digits[index]-'0'];
            
        for(char c:letters.toCharArray()){
            tmp.append(c);
            find(digits,index+1,res,tmp);
            tmp.deleteCharAt(tmp.length()-1);
        }
        return;
    }

时间复杂度：O(n)
空间复杂度：O(n)

递归与回溯法。定义一个键盘布局常量字符串数组，对应0-9数字。检查字符串是否合理（在2-9之间且只有2-9）。按输入数字顺序做递归，每次递归只取当前位置index，在布局字符串中做循环递归，加入一个字符，进入递归，退出递归后删去最后一个字符（你刚刚加进去的那个字符）。理解了递归和回溯思想还是比较容易做的。但是这个方法好像只打败了11%左右的人。有一个较快的方法是用BFS做，思路是按数字布局字符依次入队，迭代中取出队中元素与当前位置i相等长度的元素，字符串相加迭代当前位置的字符，再入队。
个人感觉复杂度是相同的，可能有一些操作是耗时的吧