# 639     Decode Ways II

## 639. [Decode Ways II](https://leetcode.com/problems/decode-ways-ii/)

## 1. Question

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

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

Beyond that, now the encoded string can also contain the character '\*', which can be treated as one of the numbers from 1 to 9.

Given the encoded message containing digits and the character '\*', return the total number of ways to decode it.

Also, since the answer may be very large, you should return the output mod 109+ 7.

**Example 1:**

```
Input: "*"
Output: 9
Explanation:
The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".
```

**Example 2:**

```
Input: "1*"
Output: 9 + 9 = 18
```

**Note:**

1. The length of the input string will fit in range \[1, 10^5].
2. The input string will only contain the character '\*' and digits '0' - '9'.

## 2. Implementation

**(1) DP**

```java
class Solution {
    long MOD = (long)1e9 + 7;
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        long[] dp = new long[2];
        dp[0] = ways(s.charAt(0));

        if (s.length() == 1) {
            return (int)dp[0];
        }

        dp[1] = dp[0] * ways(s.charAt(1)) + ways(s.charAt(0), s.charAt(1));
        for (int i = 2; i < s.length(); i++) {
            long temp = dp[1];
            dp[1] = (dp[1] * ways(s.charAt(i)) + dp[0] * ways(s.charAt(i - 1), s.charAt(i))) % MOD;
            dp[0] = temp;
        }
        return (int)dp[1];
    }

    public int ways(char c1) {
        if (c1 == '0') {
            return 0;
        }
        else if (c1 == '*') {
            return 9;
        }
        else {
            return 1;
        }
    }

    public int ways(char c1, char c2) {
        String num = "" + c1 + "" + c2;

        if (c1 != '*' && c2 != '*') {
            if (Integer.parseInt(num) >= 10 && Integer.parseInt(num) <= 26) {
                return 1;
            }
        }
        else if (c1 == '*' && c2 == '*') {
            return 15;
        }
        else if (c1 == '*') {
            if (c2 >= '0' && c2 <= '6') {
                return 2;
            }
            else {
                return 1;
            }
        }
        else {
            if (c1 == '1') {
                return 9;
            }
            else if (c1 == '2') {
                return 6;
            }
        }
        return 0;
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(1)