LeetCode 91.Decode Ways【Java】

题目描述

91. 解码方法

AC代码

/*
分类：动态规划
1.我们用数组f[i]表示前i个数字编码得到的字符串的数量，
2.f[i]的计算有两种情况：
    最后一个字母是一个数：f[i-1]
    最后一个字母是两个数：f[i-2]
3.在判断最后一个字母是两个数的时候，首先要计算一下asciⅡ是不是在[10,26]之间，但是不要忘记只有i>=2时才可能存在
一个字母可能是两个数。    
*/
class Solution {
    public int numDecodings(String s) {
        int n=s.length();
        int[] f=new int[n+1];
        f[0]=1;
        for(int i=1;i<=n;i++){
            if(s.charAt(i-1)!='0') 
                f[i]+=f[i-1];
            if(i>=2){
                int val=10*(s.charAt(i-2)-'0')+s.charAt(i-1)-'0';
                if(10<=val&&val<=26)
                    f[i]+=f[i-2];
            }
        }
        return f[n];
    }
}