给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回， 给出数字到字母的映射与电话按键相同
image
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
示例1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例2：
输入：digits = ""
输出：[]
示例3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
Java解法
思路：
- 这就是个排列组合的题，测试了下重复数字的结果，就搞完了，简单的不像中等题
- 按位求出当前的字母list，分别与上次的字母list进行了一一拼接，处理了下拼接优化，结果一把过
package sj.shimmer.algorithm;
import java.util.ArrayList;
import java.util.List;
/**
* Created by SJ on 2021/2/4.
*/
class D11 {
public static void main(String[] args) {
System.out.println(letterCombinations("22"));
}
public static List<String> letterCombinations(String digits) {
List<String> results = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return results;
}
StringBuilder builder = new StringBuilder();
List<String> temps = getLetter(Integer.parseInt(String.valueOf(digits.charAt(0))));
for (int i = 1; i < digits.length(); i++) {
List<String> letter = getLetter(Integer.parseInt(String.valueOf(digits.charAt(i))));
results.clear();
for (String s : temps) {
for (String l : letter) {
builder.delete(0, builder.toString().length());
builder.append(s);
builder.append(l);
results.add(builder.toString());
}
}
temps.clear();
temps.addAll(results);
}
results = temps;;
return results;
}
public static List<String> getLetter(int num) {
ArrayList<String> list = new ArrayList<>();
switch (num) {
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;
}
return list;
}
}
image
官方解
- 回溯
想法很高级，emmm，就是没接触过回溯思维的脑壳也能写出来
- 用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作
- 回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。
- 回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可
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); } } } }
时间复杂度：O(3^m *4^n)，其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数，m+n是输入数字的总个数。
空间复杂度： O(m+n)
