欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【Leetcode】91. 解码方法(Decode Ways)

程序员文章站 2022-07-05 14:22:55
...

Leetcode - 91 Decode Ways (Medium)

题目描述:给定一个字符串,字母 A - Z 可以分别解码成 1 - 26,求字符串共有几种解码方法。

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

解题思路:要注意 0 的问题,0 在前面与在后面计算方式不同。从后向前递推能够减少对 0 情况的判断。

public int numDecodings(String s) {
    int n = s.length();
    if (n == 0) return 0;
    
    int[] dp = new int[n + 1];
    dp[n]  = 1;
    dp[n - 1] = s.charAt(n - 1) != '0' ? 1 : 0;
    
    for (int i = n - 2; i >= 0; i--){
        if (s.charAt(i) == '0') continue;
        else dp[i] = (Integer.parseInt(s.substring(i, i + 2)) <= 26) ? dp[i + 1] + dp[i + 2] : dp[i + 1];
    }
        
    return dp[0];
}