[LeetCode] 639. Decode Ways II
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:
- The length of the input string will fit in range [1, 105].
- The input string will only contain the character '*' and digits '0' - '9'.
Thought process:
Dynamic programming.
- Sub-problem: find the total number of ways to decode a sub-string of s.
- Function:
- If s[i] == 0:
- If 0 < s[i - 1] <= 2, f[i] = f[i - 2].
- If s[i - 1] == *, * can be 1 or 2. f[i] = f[i - 2] * 2.
- Else, there is no way to decode it. Return 0.
- If s[i] > 0:
- If s[i - 1] != 0 and s[i - 1, i] <= 26, f[i] = f[i - 1] + f[i - 2].
- If s[i - 1] == *:
- If s[i] <= 6, * can be 1 or 2. f[i] = f[i - 1] + f[i - 2] * 2.
- Else, * can only be 1. f[i] = f[i - 1] + f[i - 2].
- Else, f[i] = f[i - 1].
- If s[i] == *:
- If s[i - 1] == 0, f[i] = f[i - 1] * 9.
- If s[i - 1] == 1, f[i] = f[i - 1] * 9 + f[i - 2] * 9.
- If s[i - 1] == 2, f[i] = f[i - 1] * 9 + f[i - 2] * 6.
- If s[i - 1] == *, f[i] = f[i - 1] * 9 + f[i - 2] * 15
- Else, f[i] = f[i - 1] * 9.
- Initialization: f[0] = 1.
- Answer: f[s.length()].
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | class Solution { public int numDecodings(String s) { if (s.length() == 0) { return 0; } long[] f = new long[s.length() + 1]; f[0] = 1; int M = 1000000007; for (int i = 1; i < f.length; i++) { char c = s.charAt(i - 1); char previous = '#'; if (i > 1) { previous = s.charAt(i - 2); } if (c == '0') { if (previous > '0' && previous <= '2') { f[i] = f[i - 2]; } else if (previous == '*') { f[i] = (2 * f[i - 2]) % M; } else { return 0; } } else if (c > '0') { if (previous == '*') { if (c <= '6') { f[i] = (f[i - 1] + 2 * f[i - 2]) % M; } else { f[i] = (f[i - 1] + f[i - 2]) % M; } } else if (i > 1 && previous != '0' && Integer.parseInt(s.substring(i - 2, i)) <= 26) { f[i] = (f[i - 1] + f[i - 2]) % M; } else { f[i] = f[i - 1]; } } else { f[i] = 9 * f[i - 1]; if (previous == '1') { f[i] = (f[i] + 9 * f[i - 2]) % M; } else if (previous == '2') { f[i] = (f[i] + 6 * f[i - 2]) % M; } else if (previous == '*') { f[i] = (f[i] + 15 * f[i - 2]) % M; } } } return (int) f[s.length()]; } } |
Comments
Post a Comment