这是我参与11月更文挑战的第25天,活动详情查看:2021最后一次更文挑战
电话号码的字母组合
该题出自力扣的17题——电话号码的字母组合(中等题)
审题
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
输入:digits = "23" 输出:["ad","ae","af","bd","be","bf","cd","ce","cf"] 复制代码
-
简单概括就是,需要自己维护一套数字对应的字符,就像我们日常的九宫格键盘一样,在这个的基础上,对每一个进行拼接
-
由于维护一套hashMap去存储数字对应的字符需要额外开辟空间,所以这边利用switch/case去实现
-
解决方法采用递归去实现:
- 如果当前长度为空,则直接返回空list
- 如果当前长度<2,则返回对应数字的字符
- 获取当前的字符串的首位字符去作为循环拼接
- 截取当前字符串的次位开始到末尾,进行递归遍历
- 双重for循环
- 拼接字符串
编码
回溯算法用于寻找所有的可行解,如果发现一个解不可行,则会舍弃不可行的解。在这道题中,由于每个数字对应的每个字母都可能进入字母组合,因此不存在不可行的解,直接穷举所有的解即可。
public List<String> letterCombinations(String digits) {
List<String> list = new ArrayList<>();
if (digits.isEmpty()){return list;}
else if (digits.length()<2){return matchLetter(Integer.valueOf(digits));}
List<String> nowList = matchLetter(Integer.valueOf(digits.substring(0,1)));
List<String> oldList = letterCombinations(digits.substring(1));
for (int i = 0; i < nowList.size(); i++) {
for (int j = 0; j < oldList.size(); j++) {
list.add(i,addLetter(nowList.get(i),oldList.get(j)));
}
}
return list;
}
public String addLetter(String a, String b){
StringBuilder sb = new StringBuilder(a);
sb.append(b);
return sb.toString();
}
public List<String> matchLetter(Integer a){
List<String> list = new ArrayList<>();
switch (a){
case 2:
list.add("a");
list.add("b");
list.add("c");
break;
case 3:
list.add("d");
list.add("e");
list.add("f");
break;
case 4:
list.add("g");
list.add("h");
list.add("i");
break;
case 5:
list.add("j");
list.add("k");
list.add("l");
break;
case 6:
list.add("m");
list.add("n");
list.add("o");
break;
case 7:
list.add("p");
list.add("q");
list.add("r");
list.add("s");
break;
case 8:
list.add("t");
list.add("u");
list.add("v");
break;
case 9:
list.add("w");
list.add("x");
list.add("y");
list.add("z");
break;
default:
break;
}
return list;
}
复制代码
近期评论