[C++]LeetCode: 87 Letter Combinations of a Phone Number

タイトル:
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note: Although the above answer is in lexicographical order, your answer could be in any order you want.
Answer 1:再帰法(DFS)
考え方:数字文字列の桁数に従って、DFSを1つずつ分解します.1番目の対応するアルファベットが得られたら、DFS検索を続け、数字の桁数に達するまで続けます.この結果を追加し、返します.
Attention:
1.数値アルファベットルックアップテーブルを初期化し、文字列配列で表す方法.文字列配列の1次元座標は、いくつかの文字列に位置決めされ、2次元座標は文字に位置決めされます.例えばnumap[3][2]='f'

string numap[] = {" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

2. 注意digitsが空入力の場合、空の配列ではなく「」を返します.

 string tmpstr(digits.size(), ' ');

3. もし私たちがこの時、数字2に対応する最初のアルファベットを適用したら、DFS後、数字2に対応する他のアルファベットに巧みに置き換えることができますか?もし私たちがpushを先にpopするたびに、popの最後の文字しかなく、正確に位置決めできず、同時にエラー結果が発生します.ここではindexでそれぞれ新しいアルファベットを交換します.(indexは計算digitsの何番目かを表す)

 tmpstr[index] = numap[digits[index] - '0'][i];

popを使用するエラー結果:tmpstr.pop_back();
Input:
"2"
Output:
["a","b","c"]
Expected:
["a","b","c"]
Submitted Code
AC Code:

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ret;
      //  if(digits.size() == 0) return ret;
        string tmpstr(digits.size(), ' ');
        letterCombinations_helper(digits, 0, tmpstr, ret);
        return ret;
    }
    
private:
    vector<vector<char> > phonetable;
    void letterCombinations_helper(string digits, int index, string tmpstr, vector<string>& ret)
    {
        string numap[] = {" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        if(index == digits.size())
        {
            ret.push_back(tmpstr);
            return;
        }

        for(int i = 0; i < numap[digits[index] - '0'].size(); i++)
        {
            tmpstr[index] = numap[digits[index] - '0'][i];
            letterCombinations_helper(digits, index+1, tmpstr, ret);
           // tmpstr.pop_back();
        }
        
        return;
    }
};

Answer 2:非再帰法(BFS)
構想:digitsのビット数に従って、反復的に結果を解いて、まず第1位のすべての可能性から始めて、絶えず結果を拡張します.考え方はsubsetを求めることに似ている.
例を挙げると、例えば「23」を要求し、ret=[""],2を初期化して3文字に対応するので、tmpはpushを3回行い、tmp[0]="+‘a’を得る.tmp[1] = ""+ 'b'; tmp[2] = ""+ 'c'. ret = tmp; (第1の最外層反復が終了する);ret.size() = 3. tmp[0] = "a"+ 'd'; tmp[1] = "a"+'e'; tmp[2] = "a"+'f'; tmp[3] = "b"+‘d’;.......すべての結果が得られるまで.(外層反復終了).これまでのretのすべての結果を毎回更新し、次回の反復に基づいてより多くの可能性を追加します.
この方法は理解が少し難しく、正常な思考過程に合わないかもしれませんが、プログラミングの考え方を広げることができます.
Attention:3層サイクル、最外層:digitsのビット数(digits.size()第2層:現在のret内のサブセット数(ret.size());最内層:この数字に対応するすべての可能なアルファベット(numap[digits[i]-'0').size()BFS構想です.
AC Code:

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ret(1, "");
        string numap[] = {" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        
        for(int i = 0; i < digits.size(); i++)
        {
            vector<string> tmp;
            
            for(int j = 0; j < ret.size(); j++)
            {
                for(int k = 0; k < numap[digits[i]-'0'].size(); k++)
                {
                    tmp.push_back(ret[j] + numap[digits[i]-'0'][k]);
                }
            }
            //  ret
            ret = tmp;
        }
        
        return ret;
    }
};

Submitted: 
36 minutes ago
Input:
"2"
Output:
["a","b","c"]
Expected:
["a","b","c"]
Submitted Code