当前位置:网站首页>Leecode17. Letter combination of telephone number -- 100 question series of leecodebig factory

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

2021-10-14 05:05:44 Old fellow iron has dried up the code.

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();
        }
    }
};

版权声明
本文为[Old fellow iron has dried up the code.]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/10/20211002145845239M.html

随机推荐