题目

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;

    }

};