【LeetCode】-- 17. Letter combination of telephone number

1. subject

Given a number only  2-9  String , Returns all the letter combinations it can represent . The answers can be returned in any order . The mapping of numbers to letters is given as follows （ Same as phone key ）, Be careful 1 Does not correspond to any letter ：

2. Example

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"]

3. analysis

（1） You need an array to map numbers to strings , This array does not change , Don't put it in a class , Otherwise every object will contain this array , Write it as a global

（2） Due to combination , So we should take... In turn digit The numbers in it , Combine the corresponding letters , You can use recursion

Source code ： 

class Solution {
public:
    vector<string> letterCombinations(string digits) {

    }
};

  The required return value is vector<string> Of , The return value is ret, Biography is digits, In order to get digit The value of each number in the , Recursion can be used to realize layer by layer composition , Here recursion has layers of parameters , The input parameters given by the native code are not enough , Rewrite a recursive function , The input parameter has numbers digits, The layer number i, also ret.

digits What is the length of , Just recurse a few layers , Such as digits by 236, The length is 3, Just recursion 3 layer ：

（1）i by 0 when , That is the first. 1 layer , Numbers 2 The corresponding letters abc, And then take the number 1 Letters a, Are combined

（2） The composite object is 3 The corresponding letter , At this time i need ++ become 1 To the 2 layer , The digital 3 The corresponding letter def, Cycle to the first 1 Letters d

（3） Recursive second 3 layer ,i++ Turned into 2, Numbers 6 The corresponding letter is mno, Cycle to the first 1 Letters m

Choose one letter for each layer to combine , Recursion to the last level , You get the letter combination , Cycle the last layer , And then continue the cycle 2 layer , Then go to combination No 3 layer , Until the first 2 The layer combination is completed , This is the end of the combination 1 Layer 1 Letters , Recycle the first layer , Until the combination is completed 1 All letters of the layer , All the results are combined ：

 （3） If recursion ends at the last level , Put the string combination result into the result array

4. Code implementation

// Global variables , Has been the same 
string num_str[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };

class Solution {
public:
    void _letterCombinations(const string& digits, size_t i, string str,vector<string>& ret)
    {
        // Recursion to the last level , You have successfully combined a string , Put it in the result array 
        if(i == digits.size())
        {
            ret.push_back(str);
            return;
        }
        int num = digits[i] - '0';
        const string& letters = num_str[num];// No need for deep copy , Just a light copy , So add &

        //digits No i A string corresponding to a number , Iterate according to the number of characters in the string 
        for(auto ch:letters)
        {
            _letterCombinations(digits,i+1,str+ch,ret);//str+ch Is the string being combined 
        }
    }

    vector<string> letterCombinations(string digits)
    {
        vector<string> ret;// Combined string result array 

        // Sentenced to empty 
        if(digits.empty())
        {
            return ret;
        }

        int i = 0;
        string s;// String for each combination 
        _letterCombinations(digits, i, s,ret);// Recursive Composition 
        return ret;
    }
};

Call procedure recursively ： Only with ad Call procedure for prefix letter combination , Everything else is similar to