17. 电话号码的字母组合
3 min
题目
解法：DFS回溯
思路
核心思想是深度优先搜索（DFS）回溯法，通过递归方式逐位展开数字对应的字母可能性。
正确性基于组合数学原理：每个数字对应3-4个字母，所有组合总数为各数字对应字母数的乘积。DFS递归过程中，每一层固定选择一位数字的一个字母，当递归深度达到输入长度时，恰好生成一个完整组合。由于递归会遍历每个数字对应的所有字母分支，并通过回溯机制返回上一层尝试其他选择，因此能够穷举所有可能的组合，不会遗漏任何解。
- Step 1: 建立数字到字母的映射表
- Step 2: 递归函数中，若当前索引等于输入长度，将路径加入结果
- Step 3: 否则获取当前数字对应的字母串，遍历每个字母
- Step 4: 递归调用下一层，路径添加当前字母
复杂度
- 时间复杂度:
- 空间复杂度:
代码
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
vector<string> ans;
unordered_map<char, string> mp {
{'2',"abc"}, {'3',"def"}, {'4',"ghi"}, {'5',"jkl"},
{'6',"mno"}, {'7',"pqrs"}, {'8',"tuv"}, {'9',"wxyz"}
};
dfs(mp, 0, ans, digits, "");
return ans;
}
private:
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
vector<string> ans;
unordered_map<char, string> mp {
{'2',"abc"}, {'3',"def"}, {'4',"ghi"}, {'5',"jkl"},
{'6',"mno"}, {'7',"pqrs"}, {'8',"tuv"}, {'9',"wxyz"}
};
dfs(mp, 0, ans, digits, "");
return ans;
}
private:
void dfs(unordered_map<char, string>& mp, int index, vector<string>& ans, const string& digits, string path) {
if (index == digits.size()) {
ans.push_back(path);
return;
}
string letters = mp.at(digits[index]);
for (char c : letters) {
dfs(mp, index + 1, ans, digits, path+c);
}
}
};