内容简介：想写非递归的写法，如果用深度遍历考虑的话会比较困难，需要保存中间态，可以看成不断对上一状态的广度遍历
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;
}
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
