leetcode-17 Letter Combinations of a Phone Number

題意: 給定一電話面板,上面每個數字會對應到特定幾個英文字,求一串數字所能對應到所有的字串


解題思路:其實這題算法很簡單,難的是動手實踐,舉例來說23, 2對應到a,b,c ; 3對應到d,e,f; 所以所有可能就是:
ad         
ae
af
bd
be
bf
cd
ce
cf
可發現會循環,所以就是將觀察到的規則寫出來,即所求
c++ code: 如下

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        string arr[8]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        int len=digits.length();
        vector<string> ans;
        
        if(len==0)
            return ans;
        int total=1;
       
        for(int i=0;i<len;i++)
        {
            if(digits[i]=='0'||digits[i]=='1')
                return ans;
            else if(digits[i]=='7'||digits[i]=='9')
                total=total*4;
            else
                total=total*3;
        }
        int rep=total;
        for(int i=0;i<total;i++)
            ans.push_back("");
        for(int i=0;i<len;i++)
        {
            if(digits[i]=='7'||digits[i]=='9')
            {
                int cnt=total/rep;
                rep=rep/4;
                for(int j=0;j<cnt;j++)
                {
                    for(int k=0;k<4;k++)
                    {
                        for(int n=0;n<rep;n++)
                            ans[j*rep*4+k*rep+n]+=arr[digits[i]-50][k];
                    }
                }
            }
            else
            {
                int cnt=total/rep;
                rep=rep/3;
                for(int j=0;j<cnt;j++)
                {
                    for(int k=0;k<3;k++)
                    {
                        for(int n=0;n<rep;n++)
                            ans[j*rep*3+k*rep+n]+=arr[digits[i]-50][k];
                    }
                }
            }
                
            
        }
        
        return ans;
    }
};