题目

etter-combinations-of-a-phone-number/

算法

o(n)

• 0~9中每个数字代表若干个字母，然后给一串数字，求出所有的排列组合
• 建立字典，保存每个数字所代表的字符串
• 变量level：记录当前生成的字符串的个数

代码

* 递归解法

class Solution{
public:
    vector<string> letterCominations(string digits){
        vector<string> res;
        if(digits.empty())  return res;
        string dict[]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        letterCominationsDFS(digits,dict,0,"",res);
        return res;
    }
private:
    void letterCominationsDFS(string digits,string dict[],int level,string out,vector<string>& res){
        if(level==digits.size())  res.push_back(out);
        else{
            string str=dict[digits[level]-'2'];
            for(int i=0;i<str.size();++i){
                out.push_back(str[i]);
                letterCominationsDFS(digits,dict,level,,out,res);
                out.pop_back();
            }
        }
    }
};

* 迭代的算法

class Solution{
public:
    vector<string>  letterCombinations(string digits){
        vector<string>  res;
        if(digits.empty())  return res;
        string dict[]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        res.push_back("");
        for(int i=0;i<digits.size();++i){
            int n=res.size();
            string str=dict[digits[i]-'2'];
            for(int j=0;j<n;j++){
                string tmp=res.front();
                res.erase(res.begin());
                for(int k=0;k<str.size();++k)
                    res.push_back(tmp+str[k]);
            }
        }

        return res;
    }
};