Letter Combinations of a Phone Number

编号 : 17      
难度 : <font color="orange">Medium</font>

# 题目 :  
>Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.
>
>![PhoneKeyboard](http://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Telephone-keypad2.svg/200px-Telephone-keypad2.svg.png)
>
>**Example**:
>
>>**Input**: "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.


# 解 :  
```Cpp
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        
        /* 按键对应字符串的映射 */
        map<char, string> dict = {
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"},
        };
        
        /* 最终结果 */
        vector<string> ret;
        
        if(digits.size() != 0 &&
           digits.find_first_not_of("23456789") == string::npos)
        {
            ret.push_back(""); // 作为root
        }
        else
        {
            return ret; // 输入不合法
        }
        

        /* 缓存中间过程 */
        vector<string> temp;

        for(auto& key : digits)
        {
            temp.clear();
            for(auto& ch : dict[key])
            {
                for(auto& str : ret)
                {
                    temp.push_back(str + ch);
                }
            }
            ret = temp;
        }

        return ret;
    }
};
```

# 分析 :  
这道题是一个很简单的多层循环嵌套，难点在于嵌套的层数是运行时得到的，所以不能依靠编码完成循环。

这题是一个树形结构，设输入为 "23"，则有 :  

```
2      a         b         c                
     / | \     / | \     / | \              
3   ad ae af  bd be bf  cd ce cf            
```

为了实现上述过程，用一个动态数组(A)保存输入完成一个按键的结果，嵌套遍历下一个按键上的字符和该数组，过程中用另一个动态数组(B)做缓存，遍历完成之后将B赋值给A然后清空B，再输入下一个按键。  

在上面的代码中，为了让循环可以正常展开，预先在结果里插入了一个空字符串，相当于树的根 :  

```
                                            (空字符串作为树根)
        /        |        \                 
2      a         b         c                
     / | \     / | \     / | \              
3   ad ae af  bd be bf  cd ce cf            
```