# Decode Ways

## Question ([LC.91](https://leetcode.com/problems/decode-ways/description/))

> Given a string of digits, return the number of ways that you can partition it.

## Example

Always think about edge cases before writing code. At least try 3 cases.

```
I: "12"
O: 2 because 12| or 1|2
I: "000"
O: 0
I: "02134234"
O: 0
```

## Brute Force Search

```
base case
valid single digit
return 1
valid double digit
return 1
else return 0

if valid double digit
    return decode(n-1) + decode(n-2);
else if valid single digit
    return decode(n-1)
else 
    return 0
```

## DP Approach

This is a maximization problem. We want to return the miximum number of solutions. We can clearly see some subtrees are repeating for example \[1]\[2]\[1]31 and \[12]\[1]31

```
1. define optimal subproblem
DC(n) = maximum number of ways to decode S[0:n]

2. solve by prefix
if doubleDigit(S[n-1],S[n]) <= 26
    DC(n) = DC(n-1) + DC(n-2)
else
    DC(n) = DC(n-1)

3. base case
DC(0) = 1
DC(1) = 1 if valid first digit

4. topo order
for i from 2 to n

5. final answer
DC(n)
```

## Code

```java
public int numDecodings(String digits) {
    if (digits == null || digits.length() == 0) {
        return 0;
    }
    int n = digits.length();
    // create memo table
    int[] DC = new int[n+1];
    // init base case
    DC[0] = 1;
    if (validSD(singleDigit(digits.charAt(0)))) {
        DC[1] = 1;
    }
    // topo order
    for (int i = 2; i <= n; i++) {
        int curDigit = singleDigit(digits.charAt(i-1));
        int doubleDigit = doubleDigit(digits.charAt(i-2), digits.charAt(i-1));
        if (validSD(curDigit)) { DC[i] += DC[i-1]; }
        if (validDD(doubleDigit)) { DC[i] += DC[i-2]; }
    }
    // final answer
    return DC[n];
}

private int singleDigit(char d1) {
    return d1 - '0';
}

private boolean validSD(int digit) {
    return digit >= 1 && digit <= 9;
}

private int doubleDigit(char d1, char d2) {
    return (d1 - '0') * 10 + (d2 - '0');   
}

private boolean validDD(int digit) {
    return digit >= 10 && digit <= 26;
}
```

Validating the digit turns out to be the biggest challenge of this question.

## Time & Space Complexity

O(n) time and O(n) space. Space can be constant.

## Follow Up ([LC.639](https://leetcode.com/problems/decode-ways-ii/description/))

> Now the encoded string can also contain the character '\*', which can be treated as any numbers from 1 to 9.

## Example

```
I: "*"
O: 9 because [1-9]
I: "1*"
O: 18 because 1 * [1-9] + [11-19]
I: "0*12"
O: 0
```

## Analysis