第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
0017. 电话号码的字母组合
题目地址(17. 电话号码的字母组合)
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
image.png
1
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
2
3
示例:
4
5
输入："23"
6
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
7
8
说明:
9
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
Copied!
前置知识
- 回溯
- 笛卡尔积
公司
- 阿里
- 百度
- 字节
- 腾讯
回溯
思路
由于要求所有的可能性，因此考虑使用回溯法进行求解。回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。究其本质，其实就是枚举。
如果没有更多的数字需要被输入，说明当前的组合已经产生。
如果还有数字需要被输入：
- 遍历下一个数字所对应的所有映射的字母
- 将当前的字母添加到组合最后，也就是 str + tmp[r]
关键点
- 回溯
- 回溯模板
代码
- 语言支持：JS, C++, Java, Python
JavaScript Code:
1
/**
2
* @param {string} digits
3
* @return {string[]}
4
*/
5
const letterCombinations = function (digits) {
6
if (!digits) {
7
return [];
8
}
9
const len = digits.length;
10
const map = new Map();
11
map.set("2", "abc");
12
map.set("3", "def");
13
map.set("4", "ghi");
14
map.set("5", "jkl");
15
map.set("6", "mno");
16
map.set("7", "pqrs");
17
map.set("8", "tuv");
18
map.set("9", "wxyz");
19
const result = [];
20
21
function generate(i, str) {
22
if (i == len) {
23
result.push(str);
24
return;
25
}
26
const tmp = map.get(digits[i]);
27
for (let r = 0; r < tmp.length; r++) {
28
generate(i + 1, str + tmp[r]);
29
}
30
}
31
generate(0, "");
32
return result;
33
};
Copied!
C++ Code:
1
class Solution {
2
public:
3
string letterMap[10] = {" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
4
vector<string> res;
5
vector<string> letterCombinations(string digits) {
6
if(digits == "")
7
{
8
return res;
9
}
10
dfs(digits, 0, "");
11
return res;
12
}
13
14
void dfs(string digits, int index, string s)
15
{
16
if(index == digits.length())
17
{
18
res.push_back(s);
19
return;
20
}
21
// 获取当前数字
22
char c = digits[index];
23
// 获取数字对应字母
24
string letters = letterMap[c-'0'];
25
for(int i = 0 ; i < letters.length() ; i ++)
26
{
27
dfs(digits, index+1, s+letters[i]);
28
}
29
}
30
}
Copied!
Java Code:
1
class Solution {
2
3
private String letterMap[] = {
4
" ", //0
5
"", //1
6
"abc", //2
7
"def", //3
8
"ghi", //4
9
"jkl", //5
10
"mno", //6
11
"pqrs", //7
12
"tuv", //8
13
"wxyz" //9
14
};
15
private ArrayList<String> res;
16
public List<String> letterCombinations(String digits) {
17
res = new ArrayList<String>();
18
if(digits.equals(""))
19
{
20
return res;
21
}
22
dfs(digits, 0, "");
23
return res;
24
}
25
26
public void dfs(String digits, int index, String s)
27
{
28
if(index == digits.length())
29
{
30
res.add(s);
31
return;
32
}
33
// 获取当前数字
34
Character c = digits.charAt(index);
35
// 获取数字对应字母
36
String letters = letterMap[c-'0'];
37
for(int i = 0 ; i < letters.length() ; i ++)
38
{
39
dfs(digits, index+1, s+letters.charAt(i));
40
}
41
}
42
}
Copied!
Python Code:
1
class Solution(object):
2
def letterCombinations(self, digits):
3
"""
4
:type digits: str
5
:rtype: List[str]
6
"""
7
if not digits:
8
return []
9
# 0-9
10
self.d = [" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
11
self.res = []
12
self.dfs(digits, 0, "")
13
return self.res
14
15
def dfs(self, digits, index, s):
16
# 递归的终止条件,用index记录每次遍历到字符串的位置
17
if index == len(digits):
18
self.res.append(s)
19
return
20
# 获取当前数字
21
c = digits[index]
22
# print(c, int(c))
23
# 获取数字对应字母
24
letters = self.d[int(c)]
25
# 遍历字符串
26
for l in letters:
27
# 调用下一层
28
self.dfs(digits, index+1, s+l)
Copied!
复杂度分析
N + M 是输入数字的总数
- 时间复杂度：O(2^N)，其中 N 为 digits 对于的所有可能的字母的和。
- 空间复杂度：O(2^N)，其中 N 为 digits 对于的所有可能的字母的和。
笛卡尔积
思路
不难发现， 题目要求的是一个笛卡尔积。
比如 digits = 'ab'，其实就是 a 对应的集合 {'a', 'b', 'c'} 和 b 对应的集合 {'d', 'e', 'f'} 笛卡尔积。
简单回忆一下笛卡尔积的内容。对于两个集合 A 和 B，A×B = {(x,y)|x∈A∧y∈B}。
例如，A={a,b}, B={0,1,2}，则：
- A×B={(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}
- B×A={(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)}
实际上，力扣关于笛卡尔积优化的题目并不少。 比如：
- 96.unique-binary-search-trees
- 等等
知道了这一点之后，就不难写出如下代码。
由于我们使用了笛卡尔积优化， 因此可以改造成纯函数，进而使用记忆化递归，进一步降低时间复杂度， 这是一个常见的优化技巧。
关键点
- 笛卡尔积
- 记忆化递归
代码
代码支持：Python3
1
# 输入："23"
2
# 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
3
class Solution:
4
def letterCombinations(self, digits: str) -> List[str]:
5
mapper = [" ", " ", "abc", "def", "ghi",
6
"jkl", "mno", "pqrs", "tuv", "wxyz"]
7
@lru_cache(None)
8
def backtrack(digits, start):
9
if start >= len(digits):
10
return ['']
11
ans = []
12
for i in range(start, len(digits)):
13
for c in mapper[int(digits[i])]:
14
# 笛卡尔积
15
for p in backtrack(digits, i + 1):
16
# 需要过滤诸如 "d", "e", "f" 等长度不符合的数据
17
if start == 0:
18
if len(c + p) == len(digits):
19
ans.append(c + p)
20
else:
21
ans.append(c + p)
22
return ans
23
if not digits:
24
return []
25
return backtrack(digits, 0)
Copied!
复杂度分析
N + M 是输入数字的总数
- 时间复杂度：O(N^2)，其中 N 为 digits 对于的所有可能的字母的和。
- 空间复杂度：O(N^2)，其中 N 为 digits 对于的所有可能的字母的和。
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
最近更新 1yr ago