1. 题目
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
就和我们手机的九宫格拼音一样。每个按键代表了多个字符情况。
例如：
- 2：a，b，c
- 3：d，e，f
- 4：g，h，i
- 5：j，k，l
- 6：m，n，o
- 7：p，q，r，s
- 8：t，u，v
- 9：w，x，y，z
- 0:空格
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
题目需要让我们给出组合情况值。
提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
也就是最多输入长度为4，最少可以不输入。
2. 题解
当初想到的方法很简单，从用户输入的字符串中，提取每个字符，然后进行一个拼接成数组即可：
class Solution {
public List<String> letterCombinations(String digits) {
ArrayList<String> strings = new ArrayList<>();
//得到字符
int leng = digits.length();
ArrayList<char[]> vector = new ArrayList<>();
for (int i = 0; i < leng; ++i) {
char[] s = numberToWord(digits.charAt(i));
if (s != null) {
vector.add(s);
}
}
int charNum = vector.size();
if (charNum == 0)
return strings;
char[] chars = vector.get(0);
//得到第一项数组集合
for (int i = 0; i < chars.length; ++i) {
if (charNum == 1) {
strings.add(chars[i] + "");
} else if (charNum == 2) {
xunhuan(1, strings, charNum, vector, chars[i] + "");
} else {
xunhuan(1, strings, charNum, vector, chars[i] + "");
}
}
return strings;
}
public void xunhuan(int j, ArrayList<String> s, int max, ArrayList<char[]> vector, String fz) {
//循环整个数组的长度
for (char k : vector.get(j)) {
if (j + 1 < max) {
xunhuan(j + 1, s, max, vector, fz + k);
} else {
s.add(fz + k);
}
}
}
public char[] numberToWord(char digits) {
switch (digits) {
case '2':
return new char[]{'a', 'b', 'c'};
case '3':
return new char[]{'d', 'e', 'f'};
case '4':
return new char[]{'g', 'h', 'i'};
case '5':
return new char[]{'j', 'k', 'l'};
case '6':
return new char[]{'m', 'n', 'o'};
case '7':
return new char[]{'p', 'q', 'r', 's'};
case '8':
return new char[]{'t', 'u', 'v'};
case '9':
return new char[]{'w', 'x', 'y', 'z'};
}
return null;
}
}
执行用时: 6 ms
内存消耗: 41.8 MB
计算是得到了，但是效率明显不够高。找到了下面的这种算法。效率有了显著提升：
class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if(digits == null || digits.length() == 0){
return result;
}
String[] strs = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
//1.先算出一共有几种
int len = 1;
for(int i = 0; i < digits.length(); i++){
int c = digits.charAt(i)-'0';
len *= strs[c].length();
}
//再用求余方法拿到每一种
for(int i = 0 ; i < len; i++){
int last = i;
StringBuilder sb = new StringBuilder();
for (int j=0; j< digits.length() ; ++j) {// 取字符值,每个循环就能拼接全部字数
int c = digits.charAt(j) - '0';
int pos = last % strs[c].length(); //取模得到当前字符的下标值
sb.append(strs[c].charAt(pos)); // 拼接
last = last / strs[c].length(); //循环开始第二个值
}
result.add(sb.toString());
}
return result;
}
}
执行用时: 0 ms
内存消耗: 39.8 MB
效率方法明显提高了，整个代码量也减少了不少。 下面贴官方模板代码，
class Solution {
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<String>();
if (digits.length() == 0) {
return combinations;
}
Map<Character, String> phoneMap = new HashMap<Character, String>() {{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
return combinations;
}
public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
if (index == digits.length()) {
combinations.add(combination.toString());
} else {
char digit = digits.charAt(index);
String letters = phoneMap.get(digit);
int lettersCount = letters.length();
for (int i = 0; i < lettersCount; i++) {
combination.append(letters.charAt(i));
backtrack(combinations, phoneMap, digits, index + 1, combination);
combination.deleteCharAt(index);
}
}
}
}
官方使用的是回溯。效果也是一样的。
参考链接：
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
评论区