0017. 电话号码的字母组合
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
image.png
给出数字到字母的映射如下（ 与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
- 回溯
- 笛卡尔积
- 阿里
- 百度
- 字节
- 腾讯
由于要求所有的可能性，因此考虑使用回溯法进行求解。回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。究其本质，其实就是枚举。
如果没有更多的数字需要被输入，说明当前的组合已经产生。
如果还有数字需要被输入：
- 遍历下一个数字所对应的所有映射的字母
- 将当前的字母添加到组合最后，也就是 str + tmp[r]
- 回溯
- 回溯模板
- 语言支持：JS, C++, Java, Python
JavaScript Code:
/**
* @param {string} digits
* @return {string[]}
*/
const letterCombinations = function (digits) {
if (!digits) {
return [];
}
const len = digits.length;
const map = new Map();
map.set("2", "abc");
map.set("3", "def");
map.set("4", "ghi");
map.set("5", "jkl");
map.set("6", "mno");
map.set("7", "pqrs");
map.set("8", "tuv");
map.set("9", "wxyz");
const result = [];
function generate(i, str) {
if (i == len) {
result.push(str);
return;
}
const tmp = map.get(digits[i]);
for (let r = 0; r < tmp.length; r++) {
generate(i + 1, str + tmp[r]);
}
}
generate(0, "");
return result;
};
C++ Code:
class Solution {
public:
string letterMap[10] = {" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
vector<string> res;
vector<string> letterCombinations(string digits) {
if(digits == "")
{
return res;
}
dfs(digits, 0, "");
return res;
}
void dfs(string digits, int index, string s)
{
if(index == digits.length())
{
res.push_back(s);
return;
}
// 获取当前数字
char c = digits[index];
// 获取数字对应字母
string letters = letterMap[c-'0'];
for(int i = 0 ; i < letters.length() ; i ++)
{
dfs(digits, index+1, s+letters[i]);
}
}
}
Java Code:
class Solution {
private String letterMap[] = {
" ", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};
private ArrayList<String> res;
public List<String> letterCombinations(String digits) {
res = new ArrayList<String>();
if(digits.equals(""))
{
return res;
}
dfs(digits, 0, "");
return res;
}
public void dfs(String digits, int index, String s)
{
if(index == digits.length())
{
res.add(s);
return;
}
// 获取当前数字
Character c = digits.charAt(index);
// 获取数字对应字母
String letters = letterMap[c-'0'];
for(int i = 0 ; i < letters.length() ; i ++)
{
dfs(digits, index+1, s+letters.charAt(i));
}
}
}
Python Code:
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits:
return []
# 0-9
self.d = [" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
self.res = []
self.dfs(digits, 0, "")
return self.res
def dfs(self, digits, index, s):
# 递归的终止条件,用index记录每次遍历到字符串的位置
if index == len(digits):
self.res.append(s)
return
# 获取当前数字
c = digits[index]
# print(c, int(c))
# 获取数字对应字母
letters = self.d[int(c)]
# 遍历字符串
for l in letters:
# 调用下一层
self.dfs(digits, index+1, s+l)
复杂度分析
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
# 输入："23"
# 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
mapper = [" ", " ", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"]
@lru_cache(None)
def backtrack(digits, start):
if start >= len(digits):
return ['']
ans = []
for i in range(start, len(digits)):
for c in mapper[int(digits[i])]:
# 笛卡尔积
for p in backtrack(digits, i + 1):
# 需要过滤诸如 "d", "e", "f" 等长度不符合的数据
if start == 0:
if len(c + p) == len(digits):
ans.append(c + p)
else:
ans.append(c + p)
return ans
if not digits:
return []
return backtrack(digits, 0)
复杂度分析
N + M 是输入数字的总数
- 时间复杂度：O(N^2)，其中 N 为 digits 对于的所有可能的字母的和。
- 空间复杂度：O(N^2)，其中 N 为 digits 对于的所有可能的字母的和。
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
最近更新 8mo ago