电话号码的字母组合
题目描述
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
思路
因为每多一个数字都会多很多种情况,所以直接想到了递归,从最后一位开始考虑。
那首先要打表,二维数组记录每个按键的字符
然后获取第一位digit的数字,因为传的是字符串,所以-‘0’-2就能编程数字
如果digit长度为0,返回空list
如果为1,将对应情况全部加到list中
如果大于1,则递归调用函数,从最后一位开始判断
每次循环遍历list与字符表,将新字符串添加到新list中
Java实现
public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<String>();
if(digits.length()==0){
return ans;
}
String[][] stringArr = new String[][]{
{"a", "b", "c"},
{"d", "e", "f"},
{"g", "h", "i"},
{"j", "k", "l"},
{"m", "n", "o"},
{"p", "q", "r", "s"},
{"t", "u", "v"},
{"w", "x", "y", "z"}
};
int first = digits.charAt(0)-'0'-2;
if (digits.length() == 1) {
ans.addAll(Arrays.asList(stringArr[first]));
return ans;
}
List<String> leftList = letterCombinations(digits.substring(1));
for (String ch : stringArr[first]) {
for (String str : leftList) {
ans.add(ch + str);
}
}
return ans;
}
执行用时 :2 ms, 在所有 Java 提交中击败了78.85%的用户
内存消耗 :35.6 MB, 在所有 Java 提交中击败了78.91%的用户