大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到各类媒体都在报道阿里通议将起诉前员工周畅违反竞业协议，据说周畅在离职后加入字节，职级4-2，薪资不菲，将面临巨额索赔，估计这几年打工挣的钱都不够赔。
这里科普一下什么是竞业协议，就是在离职的时候公司要求你在一段时间内不能入职存在竞争关系的公司，一般会有一份名单，当然这段时间内会给你发一笔钱作为补偿，如果你违反了这个协议会被公司起诉赔偿经济损失。最近也是经常看到员工违反竞业协议入职竞对公司被索要巨额赔偿的报道，不过这种大佬级别的被索赔还真不多见。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道高频面试题「电话号码的字母组合」。
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 ``1` 不对应任何字母。
举个例子：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
思路解析
这道题的思路就是暴力穷举所有的可能。
首先我们需要用一个哈希表保存数字和字符之间的映射关系。
假设digits = "23"，我们根据上面的映射关系可以穷举出一棵决策树。树的每条边代表一个选择，每个叶子节点代表一种组合。
这是一个标准的回溯问题，通过穷举所有可能的解来寻找满足条件解。采用深度优先搜索，从解空间的一个起始节点出发，沿着一条路径搜索解空间，如果当前路径不可能找到满足条件的解或者当前路径已经是一个满足条件的解时，就回溯到上一个节点，尝试其他的路径。重复这个过程，直到找到所有可能的解，或者解空间被完全搜索。
下面我们给出c++和python的两种代码实现。
c++代码
class Solution {
public:
vector<string> letterCombinations(string digits) {
//用来保存结果
vector<string> res;
if (digits.length() == 0)
return res;
//数字与字符串的映射
unordered_map<char, string> digit2str{
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
string tmp;
backtrack(digit2str, res, digits, 0, tmp);
return res;
}
void backtrack(unordered_map<char, string>& digit2str, vector<string>& res, string& digits, int index, string& tmp) {
//边界条件，递归深度等于字符串的长度就搜索完了一条路径
if (index == digits.length()) {
res.push_back(tmp);
return;
}
//依次搜索digits[index]对应的不同路径
for (auto c : digit2str[digits[index]]) {
tmp.push_back(c);
backtrack(digit2str, res, digits, index + 1, tmp);
tmp.pop_back();
}
}
};
python代码
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# 用来保存结果
res = []
if len(digits) == 0:
return res
# 数字与字符串的映射
digit2str = {
'2': "abc",
'3': "def",
'4': "ghi",
'5': "jkl",
'6': "mno",
'7': "pqrs",
'8': "tuv",
'9': "wxyz"
}
tmp = []
self.backtrack(digit2str, res, digits, 0, tmp)
return res
def backtrack(self, digit2str, res, digits, index, tmp):
# 边界条件，递归深度等于字符串的长度就搜索完了一条路径
if index == len(digits):
res.append("".join(tmp))
return
# 依次搜索digits[index]对应的不同路径
for c in digit2str[digits[index]]:
tmp.append(c)
self.backtrack(digit2str, res, digits, index + 1, tmp)
tmp.pop()
复杂度分析
时间复杂度： 时间复杂度跟决策树的节点总数有关。
空间复杂度： 递归会涉及到函数栈的使用，最大的递归深度跟树的高度有关，所以空间复杂度也跟决策树的高度成正比。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
