# 0091. Decode Ways

<https://leetcode.com/problems/decode-ways>

## Description

A message containing letters from `A-Z` can be **encoded** into numbers using the following mapping:

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

To **decode** an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, `"11106"` can be mapped into:

* `"AAJF"` with the grouping `(1 1 10 6)`
* `"KJF"` with the grouping `(11 10 6)`

Note that the grouping `(1 11 06)` is invalid because `"06"` cannot be mapped into `'F'` since `"6"` is different from `"06"`.

Given a string `s` containing only digits, return *the **number** of ways to **decode** it*.

The answer is guaranteed to fit in a **32-bit** integer.

**Example 1:**

```
**Input:** s = "12"
**Output:** 2
**Explanation:** "12" could be decoded as "AB" (1 2) or "L" (12).
```

**Example 2:**

```
**Input:** s = "226"
**Output:** 3
**Explanation:** "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
```

**Example 3:**

```
**Input:** s = "0"
**Output:** 0
**Explanation:** There is no character that is mapped to a number starting with 0.
The only valid mappings with 0 are 'J' -> "10" and 'T' -> "20", neither of which start with 0.
Hence, there are no valid ways to decode this since all digits need to be mapped.
```

**Example 4:**

```
**Input:** s = "06"
**Output:** 0
**Explanation:** "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
```

**Constraints:**

* `1 <= s.length <= 100`
* `s` contains only digits and may contain leading zero(s).

## ac

```java
class Solution {
    public int numDecodings(String s) {
        // edge cases
        if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;

        // dp
        int[] dp = new int[s.length()+1];
        dp[0] = 1; dp[1] = 1;
        for (int i = 2; i < dp.length; i++) {
            char curr = s.charAt(i-1);
            char prev = s.charAt(i-2);

            if (curr == '0') {
                if (prev != '1' && prev != '2') return 0;
                dp[i] = dp[i-2];
            } else {
                dp[i] += dp[i-1];
                int lastTwo = Integer.parseInt(s.substring(i-2, i));
                if (prev != '0' && lastTwo > 10 && lastTwo <= 26) dp[i] += dp[i-2];
            }
        }

        return dp[s.length()];
    }
}

/*
state: dp[i]  ways of substring(0, i)
func: 
        1) if curr char is '0', dp[i] = dp[i-2]
        2) dp[i] += dp[i-1],  if (s.charAt(i-1) >= 1 && s.substring(i-1, i+1) in [10, 26]) dp[i] += dp[i-2]
init: dp[0] = 0, dp[1] = 1
ans: dp[length]
*/
```

analyze added new char

```java
class Solution {
    public int numDecodings(String s) {
        // edge cases
        if (s == null || s.length() == 0) return 0;

        int prev = 0, curr = 1;
        for (int i = 0; i < s.length(); i++) {
            char currChar = s.charAt(i);
            char prevChar = i == 0 ? '0' : s.charAt(i-1);

            int tmp = curr;
            if (currChar == '0') {
                if (prevChar != '1' && prevChar != '2') return 0; // invalid input
                curr = prev; // last 2 must be together
            } else {
                if (prevChar == '1' || prevChar == '2' && currChar <= '6')
                    curr += prev;
            }

            prev = tmp;
        }

        return curr;
    }
}
```