【算法刷题 | 回溯思想 02】4.12（电话号码的字母组合）

本文主要是介绍【算法刷题 | 回溯思想 02】4.12（电话号码的字母组合），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

文章目录

4.电话号码的字母组合
- 4.1问题
- 4.2解法：回溯
- - 4.2.1回溯思路
  - - （1）函数返回值以及参数
    - （2）终止条件
    - （3）遍历过程
  - 4.2.2代码实现

4.电话号码的字母组合

4.1问题

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例一：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

4.2解法：回溯

4.2.1回溯思路

注意：
- 前面两个题目（组合、组合总和||）是在同一个集合中求组合
- 该题是在不同集合中求组合

List<String> res：最终返回结果
StringBuffer paths：当前路径
String[] numsString={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
}

（1）函数返回值以及参数

digits：题目给的数字字符串
cur：当前遍历的第几个数字

private void backtracking(String digits,int cur)

（2）终止条件

if( cur == digits.length() ){res.add( paths.toString() );return;
}

（3）遍历过程

String arr=numsString[ digits.charAt(cur)-'0' ];	//取出对应数字的字符串for(int i=0;i<arr.length();i++){				//遍历字符串paths.append(arr[i]);backtracking(digits,cur+1);//回溯paths.deleteCharAt(paths.size()-1);
}

4.2.2代码实现

class Solution {List<String> res=new ArrayList<>();StringBuffer paths=new StringBuffer();String[] numsString={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};public List<String> letterCombinations(String digits) {if(digits.length()==0){return res;}backtracking(digits,0);return res;}private void backtracking(String digits,int cur){if( cur == digits.length() ){res.add( paths.toString() );return;}String arr=numsString[ digits.charAt(cur)-'0' ];	//取出对应数字的字符串for(int i=0;i<arr.length();i++){				//遍历字符串paths.append(arr.charAt(i));backtracking(digits,cur+1);//回溯paths.deleteCharAt(paths.length()-1);}}
}