image.png
    image.png

    1. public int numDecodings(String s){
    2.     int len = s.length();
    3.     int[] dp = new int[len+1];
    4.     dp[len]=1;
    5.     if(s.charAt(len-1)!='0')
    6.         dp[len-1]=1;
    7.     for(int i=len-2;i>=0;i--){
    8.         if(s.charAt(i)=='0')
    9.             continue;
    10.         int ans1 = dp[i+1];
    11.         int ans2 = 0;
    12.         int ten = (s.charAt(i)-'0')*10;
    13.         int one = (s.charAt(i+1)-'0');
    14.         if(ten+one<=26)
    15.             ans2=dp[i+2];
    16.         dp[i]=ans1+ans2;
    17.     }
    18.     return dp[0];
    19. }