|
31 | 31 |
|
32 | 32 | */ |
33 | 33 | publicclass_639 { |
34 | | -/**reference: https://leetcode.com/articles/decode-ways-ii/#approach-2-dynamic-programming-accepted*/ |
35 | | -intm =1000000007; |
| 34 | +publicstaticclassSolution1 { |
| 35 | +/** |
| 36 | + * reference: https://leetcode.com/articles/decode-ways-ii/#approach-2-dynamic-programming-accepted |
| 37 | + */ |
| 38 | +intm =1000000007; |
36 | 39 |
|
37 | | -publicintnumDecodings(Strings) { |
38 | | -long[]dp =newlong[s.length() +1]; |
39 | | -dp[0] =1; |
40 | | -dp[1] =s.charAt(0) =='*' ?9 :s.charAt(0) =='0' ?0 :1; |
41 | | -for (inti =1;i <s.length();i++) { |
42 | | -if (s.charAt(i) =='*') { |
43 | | -dp[i +1] =9 *dp[i]; |
44 | | -if (s.charAt(i -1) =='1') { |
45 | | -dp[i +1] = (dp[i +1] +9 *dp[i -1]) %m; |
46 | | - }elseif (s.charAt(i -1) =='2') { |
47 | | -dp[i +1] = (dp[i +1] +6 *dp[i -1]) %m; |
48 | | - }elseif (s.charAt(i -1) =='*') { |
49 | | -dp[i +1] = (dp[i +1] +15 *dp[i -1]) %m; |
50 | | - } |
51 | | - }else { |
52 | | -dp[i +1] =s.charAt(i) !='0' ?dp[i] :0; |
53 | | -if (s.charAt(i -1) =='1') { |
54 | | -dp[i +1] = (dp[i +1] +dp[i -1]) %m; |
55 | | - }elseif (s.charAt(i -1) =='2' &&s.charAt(i) <='6') { |
56 | | -dp[i +1] = (dp[i +1] +dp[i -1]) %m; |
57 | | - }elseif (s.charAt(i -1) =='*') { |
58 | | -dp[i +1] = (dp[i +1] + (s.charAt(i) <='6' ?2 :1) *dp[i -1]) %m; |
| 40 | +publicintnumDecodings(Strings) { |
| 41 | +long[]dp =newlong[s.length() +1]; |
| 42 | +dp[0] =1; |
| 43 | +dp[1] =s.charAt(0) =='*' ?9 :s.charAt(0) =='0' ?0 :1; |
| 44 | +for (inti =1;i <s.length();i++) { |
| 45 | +if (s.charAt(i) =='*') { |
| 46 | +dp[i +1] =9 *dp[i]; |
| 47 | +if (s.charAt(i -1) =='1') { |
| 48 | +dp[i +1] = (dp[i +1] +9 *dp[i -1]) %m; |
| 49 | + }elseif (s.charAt(i -1) =='2') { |
| 50 | +dp[i +1] = (dp[i +1] +6 *dp[i -1]) %m; |
| 51 | + }elseif (s.charAt(i -1) =='*') { |
| 52 | +dp[i +1] = (dp[i +1] +15 *dp[i -1]) %m; |
| 53 | + } |
| 54 | + }else { |
| 55 | +dp[i +1] =s.charAt(i) !='0' ?dp[i] :0; |
| 56 | +if (s.charAt(i -1) =='1') { |
| 57 | +dp[i +1] = (dp[i +1] +dp[i -1]) %m; |
| 58 | + }elseif (s.charAt(i -1) =='2' &&s.charAt(i) <='6') { |
| 59 | +dp[i +1] = (dp[i +1] +dp[i -1]) %m; |
| 60 | + }elseif (s.charAt(i -1) =='*') { |
| 61 | +dp[i +1] = (dp[i +1] + (s.charAt(i) <='6' ?2 :1) *dp[i -1]) %m; |
| 62 | + } |
59 | 63 | } |
60 | 64 | } |
| 65 | +return (int)dp[s.length()]; |
61 | 66 | } |
62 | | -return (int)dp[s.length()]; |
63 | 67 | } |
64 | 68 | } |