LeetCode 17. 电话号码的字母组合

方法一：队列

思路：建立map映射，先处理第一个数字中的字符串入队，将当前队列中所有字符串拿出，跟后一个数字对应的字符匹配，重新入队。最后将队列中所有字符串压入vector

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        map<int,string> m{{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
        queue<string>q;//存放当前匹配的字符串队列
        for(int i=0;i<m[digits[0]].size();i++){//第一个数字对应字符串入队
            string str(1,m[digits[0]][i]);//将字符转换为字符串
            q.push(str);
        }
        int size=digits.size();
        for(int i=1;i<size;i++){//操作后面的数字
            int len=q.size();//对当前队列
            while(len--){
                for(int j=0;j<m[digits[i]].size();j++){//对队首字符串进行匹配后重新入队
                    string tmp=q.front();
                    tmp+=m[digits[i]][j];//匹配
                    q.push(tmp);
                }
                q.pop();//队首处理完后出队
            }  
        }
        while(!q.empty()){//队列所有字符串入向量
            ans.push_back(q.front());
            q.pop();
        }
        return ans;
    }
};