Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4digits[i] is a digit in the range ['2', '9'].
solution：
涉及全部可能的结果，使用搜索算法。
这是个排列组合问题对吧？这个排列组合可以用树的形式表示出来；
使用深度搜索算法，（问题可以看看作树的搜索问题，也可认为回溯算法）
解法思路
当给定了输入字符串，比如："23"，那么整棵树就构建完成了，如下：
{:align=center}
问题转化成了从根节点到空节点一共有多少条路径；
解法实现
关键字：
排列组合 树 递归 递归带货
实现细节：
在递归的外面有个货仓 combinations ，用来装递归过程中找到的结果；
class Solution {
public List<String> letterCombinations(String digits) {
// List<String> phoneNum2String = new ArrayList<String>(Arrays.asList("","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"));
//使用hashMap 可以应对异常边界条件，比如输入0,1或者非数字
Map<Character,String> phoneNum2String = new HashMap<>(){{
put('0', "");
put('1', "");
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
List<String> combinations = new ArrayList<>();
int index = 0;
//存当前字符串
StringBuffer current = new StringBuffer();
//算法：深度搜索 / 回溯 实现搜索，
findCombinationsBacktrack(phoneNum2String,combinations,0,digits,current);
return combinations;
}
public void findCombinationsBacktrack(Map<Character,String> phoneNum2String, List<String> combinations ,int index, String digits,StringBuffer current){
if(index == digits.length()){
if(index == 0){
return;
}
combinations.add(current.toString());
return;
}
String alphaString = phoneNum2String.get(digits.charAt(index));
for(int i = 0; i<alphaString.length();i++){
current.append(alphaString.charAt(i));
findCombinationsBacktrack(phoneNum2String,combinations,index+1,digits,current);
//注意删除上一次回溯的结果，
current.deleteCharAt(index);
}
}
}
reference：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solutions/13575/leetcode-17-letter-combinations-of-a-phone-number-/
Comments
Post a Comment