一、题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

二、示例

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

三、输入输出说明

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

四、基本思路

1）首先得到当前数字对应的字符串str

2）查询当前生成字母组合ans的第一个元素tmp（即生成字符串数组的第一个元素）

3）将1）中得到的str每个元素分别加到tmp尾部，然后添加至生成字母组合ans数组中

4）当3）遍历str结束时删除ans的第一个元素，从而更新tmp

5）循环结束条件为ans的第一个元素tmp的字符串长度大于当前数字digits下标（意味着要添加下一个数字对应的字母）

五、代码

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        ans.clear();
        if (digits.length() == 0) {
            return ans;
        }
        map<char, string> mcs;
        mcs['2'] = "abc";
        mcs['3'] = "def";
        mcs['4'] = "ghi";
        mcs['5'] = "jkl";
        mcs['6'] = "mno";
        mcs['7'] = "pqrs";
        mcs['8'] = "tuv";
        mcs['9'] = "wxyz";
        ans.push_back("");
        for (int i = 0; i < digits.length(); i++) {
            string str = mcs[digits[i]];//将要添加至尾部的字母
            string tmp = ans[0];
            while (tmp.length() == i) {
                for (int j = 0; j < str.length(); j++) {
                    ans.push_back(tmp + str[j]);
                }
                ans.erase(ans.begin());
                tmp = ans[0];
            }
        }
        return ans;
    }
};