题目链接
tag:

• Medium

question:
 &emspGiven 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.

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Example:

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

思路：
枚举所有情况。
对于每一个输入数字，对于已有的排列中每一个字符串，分别加入该数字所代表的每一个字符。

所有是三重for循环。
举例：
初始化排列{""}

1. 输入2，代表"abc"，已有排列中只有字符串""，所以得到{"a","b","c"}
2. 输入3，代表"def"

• 对于排列中的首元素"a"，删除"a"，并分别加入'd','e','f'，得到{"b","c","ad","ae","af"}

• 对于排列中的首元素"b"，删除"b"，并分别加入'd','e','f'，得到{"c","ad","ae","af","bd","be","bf"}

• 对于排列中的首元素"c"，删除"c"，并分别加入'd','e','f'，得到{"ad","ae","af","bd","be","bf","cd","ce","cf"}

注意

（1）每次添加新字母时，应该先取出现有ret当前的size()，而不是每次都在循环中调用ret.size()，因为ret.size()是不断增长的。

（2）删除vector首元素代码为：

res.erase(res.begin());

具体代码如下：

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if (digits.empty())
            return res;
        res.push_back("");
        
        vector<string> dict(10); //0-9
        dict[2] = "abc";
        dict[3] = "def";
        dict[4] = "ghi";
        dict[5] = "jkl";
        dict[6] = "mno";
        dict[7] = "pqrs";
        dict[8] = "tuv";
        dict[9] = "wxyz";
        
        for (int i=0; i<digits.size(); ++i) {
            int size = res.size();
            for (int j=0; j<size; ++j) {
                string cur = res[0];
                res.erase(res.begin());
                for (int k=0; k<dict[digits[i] - '0'].size(); ++k)
                    res.push_back(cur + dict[digits[i] - '0'][k]);
            }
        }
        return res;
    }
};