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 an encoded message containing digits, determine the total number of ways to decode it.

Example

Given encoded message 12, it could be decoded as AB (1 2) or L (12). The number of ways decoding 12 is 2.

Notes:

1. Sequence DP
2. State: f[i] the number of decode ways at index i
3. Function:
   1. f[i] += f[i-1] when the number at i-1 is valid
   2. f[i] += f[i-2] when the number at (i-2 and i-1) is valid
4. Initialize: f[0] = 1
5. Answer: f[n]

    public int numDecodings(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }

        int n = s.length();

        // state
        int[] f = new int[n+1];

        // initialize
        f[0] = 1;

        // function
        for (int i = 1; i <= n; i++) {
            if (isValid(s, i-1)) {
                f[i] += f[i-1];
            }
            if (isValid(s, i-2, i-1)) {
                f[i] += f[i-2];
            }

            if (f[i] == 0) {
                return 0;
            }
        }

        // answer
        return f[n];
    }

    private boolean isValid(String s, int i) {
        return s.charAt(i) != '0';
    }

    private boolean isValid(String s, int i, int j) {
        if (i < 0) {
            return false;
        }

        int num = (s.charAt(i)-'0')*10 + (s.charAt(j)-'0');
        return num >= 10 && num <= 26;
    }