每一个数字对应了几个字母,把数字串转化为字母串,其实就是要去枚举
可以直接使用循环按照一个数字一个数字,去枚举字母,还可以利用dfs来枚举
这里我使用map
map
第一种:循环
class Solution {
vector<string> res;
string _digits;
unordered_map<int,string> mp;
public:
vector<string> letterCombinations(string digits) {
if(digits == "") return vector<string>();
_digits = digits;
int idx = 0;
mp.insert({0,"abc"});
mp.insert({1,"def"});
mp.insert({2,"ghi"});
mp.insert({3,"jkl"});
mp.insert({4,"mno"});
mp.insert({5,"pqrs"});
mp.insert({6,"tuv"});
mp.insert({7,"wxyz"});
vector<string> v1, v2;
v1.push_back("");
for(int i = 0; i < digits.size(); i++)
{
for(auto x: v1)
{
for(auto y: mp[digits[i] - '0' - 2])
{
string s = x+y;
v2.push_back(s);
}
}
v1 = v2;
v2.clear();
}
return v1;
}
};
第二种: dfs
class Solution {
vector<string> res;
string _digits;
unordered_map<int,string> mp;
void dfs(int idx, string s)
{
if(idx == _digits.size())
{
res.push_back(s);
return;
}
for(auto x: mp[_digits[idx] - '0' - 2])
{
string ns = s + x;
dfs(idx+1, ns);
}
return;
}
public:
vector<string> letterCombinations(string digits) {
if(digits == "") return vector<string>();
_digits = digits;
int idx = 0;
mp.insert({0,"abc"});
mp.insert({1,"def"});
mp.insert({2,"ghi"});
mp.insert({3,"jkl"});
mp.insert({4,"mno"});
mp.insert({5,"pqrs"});
mp.insert({6,"tuv"});
mp.insert({7,"wxyz"});
string s = "";
dfs(idx, s);
return res;
}
};
class Solution {
vector<string> res;
vector<string> mp;
void dfs(string digits, int idx, string path)
{
if(idx == digits.size())
{
res.push_back(path);
return;
}
for(auto x: mp[digits[idx] - '0'])
{
dfs(digits, idx + 1, path + x);
}
}
public:
vector<string> letterCombinations(string digits) {
if(!digits.size()) return res;
mp = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
dfs(digits, 0,"");
return res;
}
};
第三种动态规划
class Solution {
public:
vector<string> letterCombinations(string digits) {
if(!digits.size()) return vector<string>();
vector<string> mp = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
int n = digits.size();
vector<vector<string>> f(n + 1);
f[0].push_back("");
for(int i = 1; i <= n; i++)
{
int val = digits[i - 1] - '0';
for(auto x: f[i - 1])
{
for(auto y: mp[val])
{
f[i].push_back(x + y);
}
}
}
return f[n];
}
};
第二次写题
class Solution {
public:
vector<string> letterCombinations(string digits) {
if(!digits.size()) return vector<string>();
vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> res = {""};
for(auto d: digits)
{
int n = d - '0';
vector<string> tmp;
for(auto c: v[n])
{
for(auto s: res)
{
tmp.push_back(s + c);
}
}
res = tmp;
}
return res;
}
};