|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | | -/** |
4 | | - * 91. Decode Ways |
5 | | - * |
6 | | - * A message containing letters from A-Z is being encoded to numbers using the following mapping: |
7 | | -
|
8 | | - 'A' -> 1 |
9 | | - 'B' -> 2 |
10 | | - ... |
11 | | - 'Z' -> 26 |
12 | | - Given an encoded message containing digits, determine the total number of ways to decode it. |
13 | | -
|
14 | | - For example, |
15 | | - Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12). |
16 | | -
|
17 | | - The number of ways decoding "12" is 2. |
18 | | - */ |
19 | 3 | publicclass_91 { |
20 | | -/**Credit: https://discuss.leetcode.com/topic/35840/java-clean-dp-solution-with-explanation |
| 4 | +/** |
| 5 | + * Credit: https://discuss.leetcode.com/topic/35840/java-clean-dp-solution-with-explanation |
21 | 6 | * I used a dp array of size n + 1 to save subproblem solutions. |
22 | 7 | * dp[0] means an empty string will have one way to decode, |
23 | 8 | * dp[1] means the way to decode a string of size 1. |
24 | | - * |
25 | 9 | * I then check one digit and two digit combination and save the results along the way. |
26 | | - * In the end, dp[n] will be the end result.*/ |
| 10 | + * In the end, dp[n] will be the end result. |
| 11 | + */ |
27 | 12 |
|
28 | 13 | publicstaticclassSolution1 { |
29 | | -publicintnumDecodings(Strings) { |
30 | | -if (s ==null ||s.length() ==0) { |
31 | | -return0; |
32 | | - } |
33 | | -int[]dp =newint[s.length() +1]; |
34 | | -dp[0] =1; |
35 | | -dp[1] = (s.charAt(0) !='0') ?1 :0; |
36 | | -for (inti =2;i <=s.length();i++) { |
37 | | -intfirst =Integer.valueOf(s.substring(i -1,i)); |
38 | | -intsecond =Integer.valueOf(s.substring(i -2,i)); |
39 | | -if (first >0 &&first <=9) { |
40 | | -dp[i] +=dp[i -1]; |
41 | | - } |
42 | | -if (second >=10 &&second <=26) { |
43 | | -dp[i] +=dp[i -2]; |
44 | | - } |
| 14 | +publicintnumDecodings(Strings) { |
| 15 | +if (s ==null ||s.length() ==0) { |
| 16 | +return0; |
| 17 | + } |
| 18 | +int[]dp =newint[s.length() +1]; |
| 19 | +dp[0] =1; |
| 20 | +dp[1] = (s.charAt(0) !='0') ?1 :0; |
| 21 | +for (inti =2;i <=s.length();i++) { |
| 22 | +intfirst =Integer.valueOf(s.substring(i -1,i)); |
| 23 | +intsecond =Integer.valueOf(s.substring(i -2,i)); |
| 24 | +if (first >0 &&first <=9) { |
| 25 | +dp[i] +=dp[i -1]; |
| 26 | + } |
| 27 | +if (second >=10 &&second <=26) { |
| 28 | +dp[i] +=dp[i -2]; |
| 29 | + } |
| 30 | + } |
| 31 | +returndp[s.length()]; |
45 | 32 | } |
46 | | -returndp[s.length()]; |
47 | | - } |
48 | 33 | } |
49 | 34 | } |