leetcode solution

https://leetcode.com/problems/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.

First, we need a array with length eqauls s.length() + 1, since we need to add 0 before the given string just for convience. (p.s. we will do similar thing for DP problem in many cases)

Let array nums store the value in string, array result store the decode ways for string.

There are two kinds of conditions:

1. the value in nums[i] that you are dealing with is not 0
2. the value in nums[i] that you are dealing with eqauls 0

For the first condition, since nums[i] is not 0, it can convert to a meaningful charater by itself. So the total possible decode ways, result[i], at least same as result[i - 1].
Then we consider if it is able to combine with nums[i - 1]. If the value nums[i - 1] 10 + nums[i] is greater than 10 and smaller than 26, which means nums[i - 1] 10 + nums[i] is a available value, result[i] is able to add result[i - 1]. Otherwise, it is not able to do that.

For the second condition, since nums[i] is 0, it can not convert to a meaningful character by itself. It must combine with nums[i - 1]. So we could assume nums[i - 1] * 10 + nums[i] is the value we are dealing with. the result[i] can only possibly come from result[i - 2]. The following operation is same as condition 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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