Leetcode17.电话号码的字母组合
-
题目：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
-
思路：回溯算法
-
代码如下：
class?Solution?{
? ?//设置全局存储的结果集 res
? ?List<String>??list?=?new?ArrayList<>();
?
? ?public?List<String>?letterCombinations(String?digits) {
? ? ? ?//结束条件
? ? ? ?if(digits==null||digits.length()==0){
? ? ? ? ? ?return?list;
? ? ? }
? ? ? ?//初始对应数字的字符串（0-9）0和1默认为空字符串；仍应考虑*和#输入的问题
? ? ? ?String[]?stringNum?=?{
? ? ? ? ? ?"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
? ? ? };
? ? ? ?//回溯算法
? ? ? ?backTracking(digits,stringNum,0);
? ? ? ?return?list;
?
? }
? ?//定义StringBuilder 效率更高 记录符合要求的字符串
? ?StringBuilder?tmp?=?new?StringBuilder();
? ?public?void?backTracking(String?digits,String[]?stringNum,int?num){
? ? ? ?if(digits.length()==num){
? ? ? ? ? ?list.add(tmp.toString());
? ? ? ? ? ?return?;
? ? ? }
? ? ? ?
? ? ? ?String?target?=?stringNum[(digits.charAt(num)-'0')];
? ? ? ?//遍历 回溯算法
? ? ? ?for(int?i?=0;i<target.length();i++){
? ? ? ? ? ?tmp.append(target.charAt(i));
? ? ? ? ? ?backTracking(digits,stringNum,num+1);
? ? ? ? ? ?tmp.deleteCharAt(tmp.length()-1);
? ? ? }
? }
}
