[LeetCode]17. Letter Combinations of a Phone Number

List<String> ret=new ArrayList();
List<List<Character>> list=new ArrayList(){
    {
        add(Arrays.asList('a','b','c'));
        add(Arrays.asList('d','e','f'));
        add(Arrays.asList('g','h','i'));
        add(Arrays.asList('j','k','l'));
        add(Arrays.asList('m','n','o'));
        add(Arrays.asList('p','q','r','s'));
        add(Arrays.asList('t','u','v'));
        add(Arrays.asList('w','x','y','z'));
    }
};
public List<String> letterCombinations(String digits) {
    if(digits==null || digits.length()==0) return ret;
    ref("",digits);
    return ret;
}
private void ref(String s,String digits){
    if(digits.length()==0) {
        ret.add(s);
        return;
    }
    List<Character> clist=list.get(digits.charAt(0)-'2');
    for(char c:clist){
        ref(s+c,digits.substring(1));
    }
}

想写非递归的写法，如果用深度遍历考虑的话会比较困难，需要保存中间态，可以看成不断对上一状态的广度遍历

public List<String> letterCombinations(String digits) {
    List<String> ret=new ArrayList();
    if(digits.length()<=0) return ret;
    List<List<Character>> list=new ArrayList(){
        {
            add(Arrays.asList('a','b','c'));
            add(Arrays.asList('d','e','f'));
            add(Arrays.asList('g','h','i'));
            add(Arrays.asList('j','k','l'));
            add(Arrays.asList('m','n','o'));
            add(Arrays.asList('p','q','r','s'));
            add(Arrays.asList('t','u','v'));
            add(Arrays.asList('w','x','y','z'));
        }
    };
    ret.add("");
    char[] array=digits.toCharArray();
    for(int i=0;i<array.length;i++){
        List<String> ret1=new ArrayList();
        for(char c:list.get(array[i]-'2')){
            for(String s:ret){
                ret1.add(s+String.valueOf(c));
            }
        }
        ret=ret1;
    }
    return ret;
}