[LeetCode] Decode Ways (Java)

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

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

1
2
3
4

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

Analysis

We can solve this problem recursively. But it will time out. Because we calculate the same substring several times, which is not necessary. We can use DP to make it faster.

An array nums[s.length()] is used to save the decode ways. The meaning of nums[i] is the decode way of substring of s from i to the end.

For i < s.length() – 2, if s.charAt(i) is not ‘0’, we know that nums[i] = num[i + 1], because we can decode it in this way: i, (substring from i + 1 to the end). If the value of substring (i, i + 2) satisfies 10 <= value <= 26, it means the substring can be decoded in this way: substring(i, i + 1), substring(i + 2 to the end).

Some corner cases needs to be mentioned is that there could be “”, “00” or “01”. These cases must be handled.

Code

public class Solution {
    public int numDecodings(String s) {
        if (s.length() == 0)
            return 0;
        int[] nums = new int[s.length()];
        if (s.charAt(s.length() - 1) != '0')
            nums[s.length() - 1] = 1;
        if (s.length() >= 2) {
            int value = Integer.parseInt(s.substring(s.length() - 2, s.length()));
            if (value >= 10 && value <= 26)
                nums[s.length() - 2] = nums[s.length() - 1] + 1;
            else if (s.charAt(s.length() - 2) != '0')
                nums[s.length() - 2] = nums[s.length() - 1];
            for (int i = s.length() - 3; i >= 0; i--) {
                if (s.charAt(i) != '0')
                    nums[i] = nums[i + 1];
                value = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
                if (value >= 10 && value <= 26)
                    nums[i] += nums[i + 2];
            }
        }
        return nums[0];
    }
}

public class Solution {

public int numDecodings(String s) {

if (s.length() == 0)

return 0;

int[] nums = new int[s.length()];

if (s.charAt(s.length() - 1) != '0')

nums[s.length() - 1] = 1;

if (s.length() >= 2) {

int value = Integer.parseInt(s.substring(s.length() - 2, s.length()));

if (value >= 10 && value <= 26)

nums[s.length() - 2] = nums[s.length() - 1] + 1;

else if (s.charAt(s.length() - 2) != '0')

nums[s.length() - 2] = nums[s.length() - 1];

for (int i = s.length() - 3; i >= 0; i--) {

if (s.charAt(i) != '0')

nums[i] = nums[i + 1];

value = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');

if (value >= 10 && value <= 26)

nums[i] += nums[i + 2];

}

return nums[0];

}

Complexity

The complexity is only $O(n)$.