LeetCode --- 17. Letter Combinations of a Phone Number

タイトルリンク: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.

1       2(abc)  3(def)
4(ghi)  5(jkl)  6(mno)
7(pqrs) 8(tuv)  9(wxyz)
*       0       #

For example:

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.
この問題の要求は、デジタル文字列を指定し、携帯電話のキーボードに対応するすべての可能なアルファベットの組み合わせを返すことです.ここで返される順序は任意であってもよい.
この問題の構想は比較的簡単で、反復することができて、つまり文字列の中のすべての数字を順番に読み取って、それから数字の対応するアルファベットを順番に現在のすべての結果に加えて、それから次の反復に入ります.再帰で解くこともできますが、考え方も似ています.現在存在する文字列に対して、残りの数字列を再帰し、結果を得て加算します.入力文字列には合計n個の数字があり、平均してm個の文字を表すことができると仮定すると、時間複雑度はO(m^n)であり、正確には入力文字列の各数字がアルファベット数に対応する積、すなわち結果の数、空間複雑度も同様である.
時間複雑度:O(m^n)
空間複雑度:O(m^n)
1.反復

 1 class Solution
 2 {
 3 public:
 4     vector<string> letterCombinations(string digits) //   
 5     {
 6         string d[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}, s="";
 7         vector<string> v({""});
 8         for(int i = 0; i < digits.size(); ++ i)
 9         {
10             vector<string> temp;
11             for(int j = 0; j < v.size(); ++ j)
12                 for(int k = 0; k < d[digits[i] - '0'].size(); ++ k)
13                     temp.push_back(v[j] + d[digits[i] - '0'][k]);
14             v = temp;
15         }
16         return v;
17     }
18 };

2.再帰

 1 class Solution
 2 {
 3 private:
 4     vector<string> v;
 5     void letterCombinations(string digits, int b, string s, string d[])
 6     {
 7         if(digits.size() == b)
 8             v.push_back(s);
 9         else
10             for(int i = 0; i < d[digits[b] - '0'].size(); ++ i)
11                 letterCombinations(digits, b + 1, s + d[digits[b] - '0'][i], d);
12     }
13 public:
14     vector<string> letterCombinations(string digits) //   
15     {
16         string d[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}, s="";
17         letterCombinations(digits, 0, s, d);
18         return v;
19     }
20 };

転載は出典を説明してください:LeetCode---17.Letter Combinations of a Phone Number