Letter Combinations of a Phone Number

LeetCode笔记 阅读(334)

编号 : 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            
```

Markdown使用 帮助


匿名

今天的风儿甚为喧嚣呢。

匿名

爆ぜろリアル  弾けろシナプス   バニッシュメント・ディス・ワールド!

匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善

匿名

爆ぜろリアル  弾けろシナプス   バニッシュメント・ディス・ワールド!

匿名

我有一头小毛驴,我从来也不骑。

匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善

匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善