|
| 1 | +packagecom.fishercoder.solutions; |
| 2 | + |
| 3 | +/** |
| 4 | + * 639. Decode Ways II |
| 5 | + * |
| 6 | + * A message containing letters from A-Z is being encoded to numbers using the following mapping way: |
| 7 | +
|
| 8 | + 'A' -> 1 |
| 9 | + 'B' -> 2 |
| 10 | + ... |
| 11 | + 'Z' -> 26 |
| 12 | + Beyond that, now the encoded string can also contain the character '*', |
| 13 | + which can be treated as one of the numbers from 1 to 9. |
| 14 | +
|
| 15 | + Given the encoded message containing digits and the character '*', |
| 16 | + return the total number of ways to decode it. |
| 17 | +
|
| 18 | + Also, since the answer may be very large, you should return the output mod 109 + 7. |
| 19 | +
|
| 20 | + Example 1: |
| 21 | + Input: "*" |
| 22 | + Output: 9 |
| 23 | + Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I". |
| 24 | + Example 2: |
| 25 | + Input: "1*" |
| 26 | + Output: 9 + 9 = 18 |
| 27 | +
|
| 28 | + Note: |
| 29 | + The length of the input string will fit in range [1, 105]. |
| 30 | + The input string will only contain the character '*' and digits '0' - '9'. |
| 31 | +
|
| 32 | + */ |
| 33 | +publicclass_639 { |
| 34 | +/**reference: https://leetcode.com/articles/decode-ways-ii/#approach-2-dynamic-programming-accepted*/ |
| 35 | +intM =1000000007; |
| 36 | +publicintnumDecodings(Strings) { |
| 37 | +long[]dp =newlong[s.length() +1]; |
| 38 | +dp[0] =1; |
| 39 | +dp[1] =s.charAt(0) =='*' ?9 :s.charAt(0) =='0' ?0 :1; |
| 40 | +for (inti =1;i <s.length();i++) { |
| 41 | +if (s.charAt(i) =='*') { |
| 42 | +dp[i +1] =9 *dp[i]; |
| 43 | +if (s.charAt(i -1) =='1') { |
| 44 | +dp[i +1] = (dp[i +1] +9 *dp[i -1]) %M; |
| 45 | + }elseif (s.charAt(i -1) =='2') { |
| 46 | +dp[i +1] = (dp[i +1] +6 *dp[i -1]) %M; |
| 47 | + }elseif (s.charAt(i -1) =='*') { |
| 48 | +dp[i +1] = (dp[i +1] +15 *dp[i -1]) %M; |
| 49 | + } |
| 50 | + }else { |
| 51 | +dp[i +1] =s.charAt(i) !='0' ?dp[i] :0; |
| 52 | +if (s.charAt(i -1) =='1') { |
| 53 | +dp[i +1] = (dp[i +1] +dp[i -1]) %M; |
| 54 | + }elseif (s.charAt(i -1) =='2' &&s.charAt(i) <='6') { |
| 55 | +dp[i +1] = (dp[i +1] +dp[i -1]) %M; |
| 56 | + }elseif (s.charAt(i -1) =='*') { |
| 57 | +dp[i +1] = (dp[i +1] + (s.charAt(i) <='6' ?2 :1) *dp[i -1]) %M; |
| 58 | + } |
| 59 | + } |
| 60 | + } |
| 61 | +return (int)dp[s.length()]; |
| 62 | + } |
| 63 | +} |