企业官网建设流程全解析

递归+回溯

这个题我愿称之为《回溯的入门题》。

拿到这个题直觉就是递归，既然是递归问题，还是分三步走。

step01：定义递归问题：

combine(String digits) 表示digits各个数字下字母的笛卡尔积

step02：递推关系的语义描述。

此时应该画一个图辅助推理：

digits各个数字下字母的笛卡尔积 = digits里第1个数字下面所有字母 和 剩下所有数字下字母。。。 的笛卡尔积

step03：递推关系。

combine(String digits) = for()循环遍历digits里第1个数字下面所有字母 +combine(String digits后面的数字) 。

PS: +号表示字符串的连接

不是很好描述，直接写吧。

1）这个题的难点在于那一堆形参。都是要随着递归往下传递的，要捋出来都有哪些。

2）再就是学会了回溯的巧妙写法，直接把加法运算、字符串拼接运算写到子方案参数里，这样就不用写成下面这样的“穿脱原则”了。但是仅限于值传递哈，引用传递的话只能老老实实的穿脱原则。

class Solution { public List<String> letterCombinations(String digits) { //构造递归参数，用于传递 HashMap<Character, String> map = new HashMap<>(); map.put('2',"abc"); map.put('3',"def"); map.put('4',"ghi"); map.put('5',"jkl"); map.put('6',"mno"); map.put('7',"pqrs"); map.put('8',"tuv"); map.put('9',"wxyz"); //构造递归参数，用于传递 ArrayList<String> result = new ArrayList<>(); //构造递归参数，用于传递 String temp=""; combine(digits,0,result,map,temp); return result; } public void combine(String digits,int index,ArrayList<String> result,HashMap<Character, String> map,String temp){ //2、递归出口 if(index>=digits.length()){ result.add(temp); return; } char num = digits.charAt(index); String s = map.get(num); for(int i=0;i<s.length();i++){ combine(digits,index+1,result,map,temp+s.charAt(i)); //回溯的巧妙写法index+1，以及temp+s.charAt(i) } } }