Leecode17. Letter combination of telephone number -- 100 question series of leecodebig factory

I'm Xiao Zhang , Determined to use the most concise code to do the most efficient expression


The following is my personal solution , Each problem includes all solutions as much as possible , And achieve the optimal solution , Welcome to collect ! Leaving a message. !

Portal ——>Leecode Big factory hot topic 100 Tao series problem solution


Problem description

Given a number only 2-9 String , Returns all the letter combinations it can represent . You can press In any order return .
The mapping of numbers to letters is given as follows ( Same as phone key ). Be careful 1 Does not correspond to any letter .

Example 1:
Input :digits = “23”
Output :[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

Example 2:
Input :digits = “”
Output :[]

Example 3:
Input :digits = “2”
Output :[“a”,“b”,“c”]

Tips :
0 <= digits.length <= 4
digits[i] Is the scope of [‘2’, ‘9’] A number of .


The core idea :dfs Simulated Full Permutation .

There's a little trick : Set all variables to global variables , It can avoid the high time consumption caused by passing parameters during recursion .


class Solution {

public:
vector<string> res; // An array of results 
string temp;
unordered_map<char, string> phoneMap{
 // Mapping arrays 
{
'2', "abc"},
{
'3', "def"},
{
'4', "ghi"},
{
'5', "jkl"},
{
'6', "mno"},
{
'7', "pqrs"},
{
'8', "tuv"},
{
'9', "wxyz"}
};
vector<string> letterCombinations(string digits) {

if (digits.empty()) {

return res;
}
dfs(digits, 0);
return res;
}
// to flash back 
void dfs(string digits, int step) {

if (step == digits.size()) {

res.push_back(temp);
return;
}
char digit = digits[step];
string letters = phoneMap[digit];
for(auto letter : letters) {

temp.push_back(letter);
dfs(digits, step + 1);
temp.pop_back();
}
}
};
Please bring the original link to reprint ,thank
Similar articles

2021-10-14