91. 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.

Solution:

Method 1: Dynamic Programming

This problem is similar to climb stairs. We try to solve it using dynamic programming.

We start from the beginning.

If the size of string is zero, we only have one decode way.

If the size of string is one, it depends on if it is larger than zero.

Now given any substring s.substring(0, i).

If its last digit is not zero, we know the ways to decode equals the ways to decode at s.substring(0, i - 1).                    

If its last two digit is between 10 and 26, we know the ways to decode this string equals the ways to decode at s.substring(0, i - 2).

Therefore, the ways to decode is the sum of these two.

The time complexity if O(n) and space complexity is O(n) as well. We can further optimize the space complexity to O(1) by using rolling array or two variables.



Code:

public class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] ways = new int[s.length() + 1];
        ways[0] = 1;
        ways[1] = s.charAt(0) != '0' ? 1 : 0;
        for (int i = 2; i <= s.length(); i++) {
            int one = s.charAt(i - 1) - '0';
            int two = (s.charAt(i - 2) - '0') * 10 + one;
            if (one != 0) {
                ways[i] += ways[i - 1];
            }
            if (two >= 10 && two <= 26) {
                ways[i] += ways[i - 2];
            }
        }
        return ways[s.length()];
    }
}

Method 2: Optimized with rolling array

We only need two previous status to decide the current value.

The space complexity is optimized to O(1).



Code:

public class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }    
        int[] ways = new int[2];
        ways[0] = 1;
        ways[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2 ;i <= s.length(); i++) {
            int one = s.charAt(i - 1) - '0';
            int two = (s.charAt(i - 2) - '0') * 10 + one;
            int curr = 0;
            if (one != 0) {
                curr += ways[(i - 1) % 2];
            }
            if (two >= 10 && two <= 26) {
                curr += ways[(i - 2) % 2];
            }
            ways[i % 2] = curr;
        }
        return ways[s.length() % 2];
    }
}