电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
循环&迭代&回溯&递归&递推这些基本概念
1 初步解析
循环：不断重复进行某一运算、操作。
迭代：不断对前一旧值运算得到新值直到达到精度。一般用于得到近似目标值，反复循环同一运算式（函数），并且总是把前一 次运算结果反代会运算式进行下一次运算
递推：从初值出发反复进行某一运算得到所需结果。-----从已知到未知，从小到达（比如每年长高9cm，20年180，30后270）
回溯：递归时经历的一个过程。
递归：从所需结果出发不断回溯前一运算直到回到初值再递推得到所需结果----从未知到已知，从大到小，再从小到大(你想进bat，那么编程就的牛逼，就得卸载玩者农药，努力学习）。递归(Recursion)是从归纳法(Induction)衍生出来的。
2 深度解析
递归是一个树结构，从字面可以其理解为重复“递推”和“回归”的过程，当“递推”到达底部时就会开始“回归”，其过程相当于树的深度优先遍历。
迭代是一个环结构，从初始状态开始，每次迭代都遍历这个环，并更新状态，多次迭代直到到达结束状态。
理论上递归和迭代时间复杂度方面是一样的，但实际应用中（函数调用和函数调用堆栈的开销）递归比迭代效率要低。
3回溯法：
也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解过程，回溯到上一步寻找其他求解路径。
为了能够撤销当前的求解过程，必须保存上一步以来的求解路径，这一点相当重要。
自己二刷的代码
class Solution {
List<String> returnlist = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if(digits == null || digits.length() == 0){
return returnlist;
}
StringBuilder sb2 = new StringBuilder();
helper(0,sb2,digits);
return returnlist;
}
public void helper(int index,StringBuilder sb,String digits){
if(digits.length() == index){
returnlist.add(sb.toString());
return;
}
String values =ToString(digits.charAt(index));
for(char c : values.toCharArray()){
sb.append(c);
helper(index+1,sb,digits);
sb.deleteCharAt(sb.length()-1);
}
}
public String ToString(char digits){
String retr = "";
switch(digits){
case '2':
retr = "abc";
break;
case '3':
retr = "def";
break;
case '4':
retr = "ghi";
break;
case '5':
retr = "jkl";
break;
case '6':
retr = "mno";
break;
case '7':
retr = "pqrs";
break;
case '8':
retr = "tuv";
break;
case '9':
retr = "wxyz";
break;
default:
retr = "wrong";
}
return retr;
}
}一 方法：回溯
回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算***舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。
把每个数字当作递归的一层，每一层中先枚举一个字母，
递归进入下一层，再删除这个字母，回到上一个状态，枚举下一个字母。
递归结束标志是递归了digits.lengtgh层，即字母组合长度等于digits长度，
递归结束得到一个符合的字母组合，加入list。等于是在循环中套递归
public class Main {
static Map<String, String> phone = new HashMap<String, String>() {
{
put("2", "abc");
put("3", "def");
put("4", "ghi");
put("5", "jkl");
put("6", "mno");
put("7", "pqrs");
put("8", "tuv");
put("9", "wxyz");
}};
static List<String> output = new ArrayList<String>();
public static void main(String[] args) {
System.out.println("请输入数字");
Scanner sc = new Scanner(System.in);
//方式1
String str = sc.nextLine();
System.out.println(letterCombinations(str.substring(1,str.length()-1)));
}
public static List<String> letterCombinations(String digits) {
if (digits.length() != 0)
backtrack("", digits);
return output;
}
//combination表示目前已经产生的组合 next_digits接下来准备要输入的数字
public static void backtrack(String combination, String next_digits) {
if (next_digits.length() == 0) {
output.add(combination);
}
else {
String digit = next_digits.substring(0, 1);
String letters = phone.get(digit);
//这里已经得到了当前digit所对应的字符串，然后对其进行遍历
for (int i = 0; i < letters.length(); i++) {
//比如这里得到数字2的字母。abc
String letter = phone.get(digit).substring(i, i + 1);
//首先letter是a
backtrack(combination + letter, next_digits.substring(1));
//在letter是啊的情况下进行遍历 数字3
}
}
}
二 树的深度优先搜索
/**
* @Auther: liuhaidong
* Data: 2019/9/22 0022、11:47
* Description://运用dfs方法
* @version: 1.0
*/
public class letterCombinations {
public static void main(String[] args) {
System.out.println("请输入数字");
Scanner sc = new Scanner(System.in);
//方式1
String str = sc.nextLine();
System.out.println(letterCombinations(str.substring(1,str.length()-1)));
}
public static List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if(digits == null || digits.length() == 0){
return res;
}
StringBuilder sb = new StringBuilder();
//这里用StringBuilder的作用是
Map<Integer,String> dict = constructWordDist();
dfsHelper(digits,0,dict,sb,res);
//四个参数第一个是字符串，第二个是当前树的索引，第三个是当前的数字，第四个是添加字符。第五个是传进来的List数组返回值
return res;
}
private static void dfsHelper(String digits, int index ,Map<Integer,String> dict,StringBuilder sb, List<String> res){
if(index == digits.length()){
//到了最后了返回
res.add(sb.toString());
return ;
}
int ch = digits.charAt(index) - '0';
//当前对应的是什么
String values = dict.get(ch);
//这里是拿到树的第index层
for(char c : values.toCharArray()){
//分别取这一次的字符数组
sb.append(c);
dfsHelper(digits,index+1,dict,sb,res);
//进入下一次
sb.deleteCharAt(sb.length()-1);
//记得把最后一个删除掉，这样才能重新进入树的第二层
}
}
private static Map<Integer,String> constructWordDist(){
Map<Integer,String> wordDist = new HashMap<>();
wordDist.put(0,"");
wordDist.put(1,"");
wordDist.put(2,"abc");
wordDist.put(3,"def");
wordDist.put(4,"ghi");
wordDist.put(5,"jkl");
wordDist.put(6,"mno");
wordDist.put(7,"pqrs");
wordDist.put(8,"tuv");
wordDist.put(9,"wxyz");
return wordDist;
}
京公网安备 11010502036488号