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.
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
