LeetCode17-Letter-Combinations-of-a-Phone-Number

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.

是一个不定层的循环问题,而且内层要有外层的状态
可以通过递归解决

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;}