题目介绍
题目:电话号码的字母组合
描述:给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
数字字母映射示例:
- 输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].说明: 尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。
解析
如果还记得高中学过的排列组合问题,就可以发现以上问题是一个最简单的组合问题。假设输入了 n 个数字,每个数字所包含的字母个数分别是 m1, m2, ..., mn,那么解的个数则为:C1m1C1m2...C1mn ,也就是m1*m2*...*mn。虽然这和我们的题目关系不大,但是它限定了时间复杂度的下限,我们在设计算法时可以参考此值。
首先,我们考虑最简单的情况,假如只输入一个数字 2,那么答案的解集是{"a", "b", "c"},现在,我们输入第二个数字 3,那就是把 "d"、"e"、"f" 分别和 "a" 组合,然后和 "b" 组合,最后再与 "c" 组合。也就是说,我们得到前面的结果,复制多份,每一个结果后都增加一个当前的字符,就可以得到最终结果,由此可以得出第一条思路:递归。参考代码如下:
public List<String> letterCombinations(String digits) {
if(digits.length()==0)return new ArrayList<>();
String[] letters = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
return letterCombinations(digits,letters,digits.length()-1);
}
private List<String> letterCombinations(String digits,String[] letters, int end) {
List<String> result = new ArrayList<>();
if (end==0) {
int index = digits.charAt(end)-'2';
for (int i = 0; i < letters[index].length(); i++) {
result.add(String.valueOf(letters[index].charAt(i)));
}
return result;
}else{
int index = digits.charAt(end)-'2';
for (int i = 0; i < letters[index].length(); i++) {
// 复制前一结果
List<String> temp = new ArrayList<>(letterCombinations(digits, letters, end-1));
for (int j = 0; j < temp.size(); j++) {
// 每一条结果后边都加上当前的一个字符
temp.set(j, temp.get(j)+letters[index].charAt(i));
}
result.addAll(temp);
}
}
return result;
}
但是以上的代码并不完美,为了复制递归需要的数据,额外的执行了一段for循环语句,大大增加了时间复杂度,而且由于无法使用StringBuilder等类来操作字符串的拼接,额外创建了许多String变量,又浪费了大量的时间和空间。所以我们需要寻找一种能够使用StringBuilder,又不需要多一层for循环的方法,这个方法就是:递归+回溯。
现在依然假设输入了数字 2,因为还要输入更多的数字,所以这时还得不到最终结果,我们从数字 2 代表的结果中选择一个字符存入到StringBuilder里,例如选择了字符 'a',现在StringBuilder里的结果就是 'a'。接下来输入数字 3 之后,'d'、'e'、'f' 每个字符都要和 'a' 组合,那么我们可以把 'a' 固定在StringBuilder中,加入 'd' 组成结果 "ad",然后移除 'd' 再加入 'e',组成结果 'ae',...。假如输入了更多数字,就依法炮制,再固定 "ad",然后加入 'g' 组成 "adg",移除 'g' 再加入 'h' 组成 "adh",...。这个过程就是回溯,之所以还有递归是因为每次运算只处理了一个输入的数字。参考代码如下:
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if(digits.length()==0)return result;
String[] letters = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
StringBuilder sb = new StringBuilder();
letterCombinations(digits, 0, letters, sb, result);
return result;
}
private void letterCombinations(String digits, int start,String[] letters, StringBuilder sb, List<String> result){
if(start==digits.length()){
if (sb.length()>0) {
result.add(sb.toString());
}
return;
}
if (digits.charAt(start)>='2'&&digits.charAt(start)<='9'){
for (int i = 0; i < letters[digits.charAt(start)-'2'].length(); i++) {
// 加入一个字符
sb.append(letters[digits.charAt(start)-'2'].charAt(i));
// 进入下一级运算
letterCombinations(digits, start+1, letters, sb, result);
// 删除最后加入的字符
sb.deleteCharAt(sb.length()-1);
}
}else{
letterCombinations(digits, start+1, letters, sb, result);
}
}
可以看到递归+回溯算法的实现十分简洁,但是也较为抽象。接下来我们就以示例为例,看看输入字符串为 "23" 时,代码是如何执行的。
首先,获取到字符 '2' 时,函数进到第一轮,代码走到for循环中时把字符 'a' 添加到了 sb(StringBuilder实例)对象中,然后就进入了函数的第二轮,for循环将等待此递归函数执行完成后再继续运行。这时获取到字符 '3',又把字符 'd' 添加到了sb中,进入了下一轮的递归,也就是函数的第三轮。
第三轮已经得到了完整的结果,便return了,这时第二轮的函数继续执行,它把 sb 中的最后一个字符删除,于是 sb 中又只剩下 'a',for循环重复这个过程之后,就得到了三个结果,分别是 "ad","ae","af"。
现在,第二轮的函数结束了,sb 中依然只剩下字符 'a',回到第一轮时继续执行删除语句,便把 'a' 也删除了,然后继续处理 'b'、处理 'c',便得到了全部结果。
总结
其实早在研究KMP算法时,我们就见到过回溯的身影,之所以有KMP算法就是为了解决暴力算法的回溯问题,当然不是任何情况下都能避免回溯的。
递归+回溯能够解决很多实际的问题,之后的许多题目都可以用这个思路来解决,但是这个算法较为抽象,需要我们多多练习,才能深刻理解。
相关源码已经上传到我的Github。
下题预告
题目:四数之和
描述:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。
注意:答案中不可以包含重复的四元组。
示例:
给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。
满足要求的四元组集合为:[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
本文到此就结束了,如果您喜欢我的文章,可以关注我的微信公众号: 大大纸飞机
或者扫描下方二维码直接添加:
公众号您也可以关注我的github:https://github.com/LtLei/articles
编程之路,道阻且长。唯,路漫漫其修远兮,吾将上下而求索。
网友评论