首页 > 代码库 > Decode ways

Decode ways

2024-07-13 11:49:19   221人阅读

用了一个多小时，根据测试用例如果当前为0，前面必须为1，或者2，并且两者组合成一个dp[i]=dp[i-2];其他情况就简单一些，一定能dp[i-1]和这个单独，可能d[i-2]

 1 public class Solution { 2     public boolean isTwo(int a,int b) 3     { 4         int ans=a*10+b; 5         if(ans>=11&&ans<=26) return true; 6         return false; 7          8          9         10     }11 12     public int numDecodings(String s) {13         char c[]=s.toCharArray();14         int len=c.length;15         16         if(len==0) return 0;17         if(c[0]==‘0‘) return 0;18         if(len==1) return 1;19         20         int dp[]=new int[len+3];21         //dp[0]=0;A22         dp[0]=1;// the len==123        if(c[1]==‘0‘)24        {  25            if(c[0]==‘1‘||c[0]==‘2‘) dp[1]=1;26            else  return 0;27            28        }29         else30         {31             if(isTwo(c[0]-‘0‘,c[1]-‘0‘))dp[1]=2;32             else   dp[1]=1;33             34         }35 36         for(int i=2;i<len;i++)37         {   38             if(c[i]==‘0‘)39             {40                 if(c[i-1]==‘1‘||c[i-1]==‘2‘)41                 {42                 dp[i]=dp[i-2]; continue;43                 }44                 else  return 0;45                 46             }47             else48             {49             50             51             dp[i]+=dp[i-1];52             if(isTwo(c[i-1]-‘0‘,c[i]-‘0‘)) dp[i]+=dp[i-2];53             }54             55             56         }57         58         59         60       return dp[len-1];61         62         63     }64 }
View Code


联系
我们