LeetCode - Decode Ways | Darren's Blog

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.
Transformation function as:
Count[i] = Count[i-1]  if S[i-1] is a valid char
       or   = Count[i-1]+ Count[i-2]  if S[i-1] and S[i-2] together is still a valid char.

public int numDecodings(String s) {

        if (s == null || s.length() == 0)

            return 0;

        int n = s.length();

 

        // table[i]: the number of decodings for s[i...]

        int[] table = new int[n+1];

        // table[n]: upon reaching the end, earlier digit(s) is a way of decoding itself

        // It is used to handle the cases such as s="15"

        table[n] = 1;

 

        // Consider the last digit individually

        char last = s.charAt(n-1);

        if (last >= '1' && last <= '9')

            table[n-1] = 1;

 

        // Calculate table[i] according to s[i], table[i+1], and table[i+2]

        for (int i = n-2; i >= 0; i--) {

            char c = s.charAt(i);

            if (c < '1' || c > '9')     // s[i...] starts with invalid digit

                table[i] = 0;

            else if (c > '2' || c == '2' && s.charAt(i+1) > '6')    // s[i,i+1] must be decoded together

                table[i] = table[i+1];

            else    // Decoded as s[i], s[i+1...], or s[i,i+1], s[i+2...]

                table[i] = table[i+1] + table[i+2];

        }

 

        // Return the number of decodings for s

        return table[0];

    }

Read full article from LeetCode - Decode Ways | Darren's Blog