LeetCode: 91. Decode Ways

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

91. Decode Ways

LeetCode - Decode Ways

这道题可以使用动态规划算法解决。学习《算法导论》中"动态规划"的解题步骤，再推演几次这个解题方法。

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Runtime: 3 ms, faster than 19.41% of Java online submissions for Decode Ways.
 *
 * Memory Usage: 41.5 MB, less than 5.66% of Java online submissions for Decode Ways.
 *
 * Copy from: https://leetcode.com/problems/decode-ways/discuss/30357/DP-Solution-(Java)-for-reference[DP Solution (Java) for reference - LeetCode Discuss]
 */
public int numDecodings(String s) {
    if (Objects.isNull(s) || s.length() == 0) {
        return 0;
    }
    int length = s.length();
    int[] memo = new int[length + 1];
    memo[length] = 1;
    memo[length - 1] = s.charAt(length - 1) != '0' ? 1 : 0;
    for (int i = length - 2; i >= 0; i--) {
        if (s.charAt(i) == '0') {
            continue;
        } else {
            int value = Integer.parseInt(s.substring(i, i + 2));
            memo[i] = value <= 26 ? memo[i + 1] + memo[i + 2] : memo[i + 1];
        }
    }
    return memo[0];
}