題意: 給定一電話面板,上面每個數字會對應到特定幾個英文字,求一串數字所能對應到所有的字串
解題思路:其實這題算法很簡單,難的是動手實踐,舉例來說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; } };
沒有留言:
張貼留言