Decode Ways（C++解码方法）

以你之姓@ 2022-10-12 01:03 232阅读 0赞

（1）递归，超时

  1. class Solution {
  2. public:
  3.     int helper(string &s,int l) {
  4.         if(l==s.length()-1 && s[l]!='0') return 1;
  5.         else if(l==s.length()-1) return 0;
  6.         if(l>=s.length()) return 1;
  8.         string str="";
  9.         int temp,sum=0;
  10.         for(int i=l;i<s.length();i++) {
  11.             str.push_back(s[i]);
  12.             temp=stoi(str);
  13.             if(temp==0) return sum;
  14.             else if(temp<=26) sum+=helper(s,i+1);
  15.             else return sum;
  16.         }
  17.         return sum;
  18.     }
  19.     int numDecodings(string s) {
  20.         return helper(s,0);
  21.     }
  22. };

（2）动态规划

  1. class Solution {
  2. public:
  3.     int numDecodings(string s) {
  4.         int m=s.length();
  5.         vector<int> v(m+1,0);
  6.         v[0]=1;
  8.         for(int i=1;i<m+1;i++) {
  9.             if(i-2>=0 && s[i-2]!='0' && (10*(s[i-2]-'0')+(s[i-1]-'0'))<=26)
  10.                 v[i]+=v[i-2];
  11.             if(s[i-1]!='0') 
  12.                 v[i]+=v[i-1];
  13.         }
  14.         return v[m];
  15.     }
  16. };

发表评论

表情：
评论列表 （有 0 条评论，232人围观）

还没有评论，来说两句吧...

相关阅读