首页 > 代码库 > LeetCode | #17 Letter Combinations of a Phone Number
LeetCode | #17 Letter Combinations of a Phone Number
题目：
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
思路：
- 其实就是要遍历所有可能，从每个数字对应的字母中选一个，搭配在一起，如果用暴力枚举的话，还真不好搞而且会超时；
- 递归，关键的是要找规则，规则如下：
//digits-号码串 i-号码串的下标 temp-临时字符串 res-返回值 public void dfs(String digits, int i, String temp, List<String> res)
- 初始条件：从号码串的第一个数字开始，定义临时字符串“”，定义要返回的List，开始递归，dfs(digits, 0, "", res)；
- 如果号码串遍历完了，就返回List，否则获取该数字对应的字符串，遍历每个字母，添加到临时字符串中，并从号码串的下一个数字开始，递归调用，dfs(digits, i+1, temp2, res)；
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class LetterCombinations {
HashMap<Integer, String> map = new HashMap<Integer, String>(){
{
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");
}
};
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
dfs(digits, 0, "", res);
return res;
}
//digits-号码串 i-号码串的下标 temp-临时字符串 res-返回值
public void dfs(String digits, int i, String temp, List<String> res){
if(i == digits.length()){
res.add(temp);
return;
}
String s = map.get(digits.charAt(i)-'0');
for(int j=0; j< s.length(); j++){
String temp2 = temp +s.charAt(j);
dfs(digits, i+1, temp2, res);
}
}
}LeetCode | #17 Letter Combinations of a Phone Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。