# [LeetCode 91] Decode Ways

### Question

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.

### Stats

 Frequency 4 Difficulty 3 Adjusted Difficulty 3 Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

This question is easy to think, but hard to write.

Why? Because there are a lot of cases that the decode ways = 0. For example, input = “02” or “50”. We must handle those cases well. Also, boundary cases can cause some trouble.

### Solution

DP solution, the transformation function is:

Count[i] = Count[i-1] if only S[i-1] is valid

Count[i] = Count[i-1] + Count[i-2] if S[i-1] and S[i-2] both valid

### Code

First, my code.

``````public int numDecodings(String s) {
int len = s.length();
if (len == 0) return 0;
// now len >= 1
int[] dp = new int[len];
if (s.charAt(0) == '0') dp[0] = 0;
else dp[0] = 1;
if (len == 1) return dp[0];
// now len >= 2
for (int i = 1; i < len; i ++) {
if (s.charAt(i) != '0') dp[i] += dp[i-1];
int doubleDigit = Integer.parseInt(s.substring(i-1, i+1));
if (s.charAt(i-1) != '0' && 1 <= doubleDigit && doubleDigit <= 26)
if (i != 1) dp[i] += dp[i-2];
else dp[i] += 1;
}
return dp[len - 1];
}
``````

Second, code from this blog.

The only difference is an additional ‘1’ at position 0 of the dp array. This helps simply the code a lot!

``````public int numDecodings(String s) {
int n = s.length();
if (n==0) return 0;
int[] dp = new int[n+1];
dp[0] = 1;
if (isValid(s.substring(0,1))) dp[1] = 1;
else dp[1] = 0;
for(int i=2; i<=n;i++){
if (isValid(s.substring(i-1,i)))
dp[i] = dp[i-1];
if (isValid(s.substring(i-2,i)))
dp[i] += dp[i-2];
}
return dp[n];
}

public boolean isValid(String s){
if (s.charAt(0)=='0') return false;
int code = Integer.parseInt(s);
return code>=1 && code<=26;
}
``````