leetcode 639 Decode Ways II

<!–

(adsbygoogle=window.adsbygoogle||[]).push({})

–>

(adsbygoogle=window.adsbygoogle||[]).push({})

<!–
–>

首先回顾一下decode ways I 的做法：链接

分情况讨论

if s[i]==\’*\’

　　考虑s[i]单独decode，由于s[i]肯定不会为0，因此我们可以放心的dp+=dp1

　　再考虑s[i-1]和s[i]decode，如果s[i-1]为*，那么**的组合共有15种(11,12,13…..,21,22..26)，注意不是9*9=81种，因为我们是s[i-1]和s[i]一起decode，如果是38这样是大于26的

　　　　　　　　　　　　　　如果s[i-1]不为*，枚举s[i]，组合起来小于26即可

if s[i]!=\’*\’

　　考虑s[i]单独decode,　　和decode ways I 一样，考虑s[i]为0的情况

　　再考虑s[i-1]和s[i] decode　如果s[i-1]为*, 那么 *和s[i]组合要小于26，直接枚举判断就行了

　　　　　　　　　　　　　　如果s[i-1]不为*，枚举s[i-1]，组合起来小于26即可

不用条件运算符会更快，但用了代码会简洁很多

 class Solution {

 public:

     int numDecodings(string s) {

         int n=s.length();

         if(n==)    return ;

         vector<int> dp(n+,);

         long long dp1=,dp2=,now;

         if(s[]!=\'\')   dp1=s[]==\'*\'?:;

         for(int i=;i<n;i++){

             if(s[i]==\'*\'){

                 now=dp1*;

                 if(s[i-]==\'*\') now+=i-<?:dp2*;

                 else{

                     for(int j=;j<;j++){

                         if(s[i-]!=\'\'&&((s[i-]-\'\')*+j<=))    now+=i-<?:dp2;

                     }

                 }

             }

             else{

                 now=s[i]==\'\'?:dp1;

                 if(s[i-]==\'*\'){

                     for(int j=;j<;j++){

                         if(j*+s[i]-\'\'<=)   now+=i-<?:dp2;

                     }

                 }

                 else{

                     if(s[i-]!=\'\'&&((s[i-]-\'\')*+s[i]-\'\'<=)) now+=i-<?:dp2;

                 }

             }

             dp2=dp1%();

             dp1=now%();

         }

         return (int)dp1;

     }

 };