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.

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.

Use DP to store for the current processed string, how many ways to decode the string.

The idea is to check whether current digit can be decoded, then also check whether the previous+current digit can be decoded then add them together.

10 - 1 way

100 - 0 way

12 - 2 ways

public boolean isValidDigits(String str) {
        if (str.startsWith("0")) {
            return false;
        }

        int num = Integer.parseInt(str);
        if (num>0&&num<=26) {
            return true;
        }
        return false;
    }

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

        int[] results = new int[str.length()];       
        results[0] = 1;

        for (int i=1; i<str.length(); i++) {
            String current = str.substring(i, i+1);
            if (isValidDigits(current)) {
                results[i] = results[i-1];
            }

            String previousAndCurrent = str.substring(i-1, i+1);
            if (isValidDigits(previousAndCurrent)) {
                if (i>1) {
                    results[i] += results[i-2];
                } else {
                    results[i] += results[i-1];
                }                
            }
        }

        return results[str.length()-1];
    }