Decode Ways | Leetcode

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

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

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

---

Solution: Use the dynamic programming formula f[i] = f[i - 1] + f[i - 2] (f is given as "ways" in the code). But it is not straightforward. You can add f[i - 1] only if the current digit is a valid standalone code (0..9), else you cannot add f[i - 1]. You can add f[i - 2] only if the previous digit (i - 1) and the current digit forms a valid code (10..26), else you cannot add f[i - 2]. We start from 10 (in 10..26) because if it starts from 0, then it will be accounted for by f[i - 1]. Hence it cannot be double-counted.

Setting the first two counts f[0] and f[1] is not trivial. If f[0] is a standalone code (1..9), then we have at least 1 way, hence set f[0] = 1, else f[0] = 0. If f[0] and f[1] forms a standalone code (10..26), then we have at least 1 way, hence set f[1] = 1, else f[1] = 0. If both f[0] and f[1] are standalone codes (1..9), then we get one more way at position f[1], hence f[1]++.

From the base values f[0] and f[1], iterate through the string and apply the formula f[i] = f[i - 1] + f[i - 2] accordingly. The answer will be stored in the last element of f.

public class Solution {
    private boolean isValid(int ch) {
        // True if 1 <= num <= 9.
        return ch >= '1' && ch <= '9';
    }

    private boolean isValid(int ch1, int ch2) {
        // True if 10 <= num <= 26.
        return (ch1 == '1' && ch2 >= '0' && ch2 <= '9')
                || (ch1 == '2' && ch2 >= '0' && ch2 <= '6');
    }

    public int numDecodings(String s) {
        if (s.length() == 0) return 0;
        
        int[] ways = new int[s.length()];
        
        // Set ways[0].
        if (isValid(s.charAt(0))) ways[0]++;
        if (s.length() == 1) return ways[0];
        
        // Set ways[1].
        if (isValid(s.charAt(0)) && isValid(s.charAt(1))) ways[1]++;
        if (isValid(s.charAt(0), s.charAt(1))) ways[1]++;
        
        // ways[i] = ways[i - 1] + ways[i - 2] with checking.
        for (int i = 2; i < s.length(); i++) {
            if (isValid(s.charAt(i))) ways[i] = ways[i - 1];
            if (isValid(s.charAt(i - 1), s.charAt(i))) ways[i] += ways[i - 2];
        }
        
        return ways[s.length() - 1];
    }
}