Decode Ways

Question (LC.91)

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

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)

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