Letter Combinations of a Phone Number
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
class Solution {
public:
vector<string> letterCombinations(string digits)
{
vector<string> res;
if(digits.length() == 0)
{
return res;
}
map<char, vector<string>> hash;
hash['2'] = {"a", "b", "c"};
hash['3'] = {"d", "e", "f"};
hash['4'] = {"g", "h", "i"};
hash['5'] = {"j", "k", "l"};
hash['6'] = {"m", "n", "o"};
hash['7'] = {"p", "q", "r", "s"};
hash['8'] = {"t", "u", "v"};
hash['9'] = {"w", "x", "y", "z"};
string cur = "";
dfs(res, cur, hash, digits, 0);
return res;
}
void dfs(vector<string>& res, string& cur, map<char, vector<string>>& hash, string digits, int pos)
{
if(pos >= digits.length())
{
res.push_back(cur);
return ;
}
for(string str : hash[digits[pos]])
{
cur.append(str);
dfs(res, cur, hash, digits, pos+1);
cur.pop_back();
}
}
};