|
29 | 29 |
|
30 | 30 | */ |
31 | 31 | publicclass_241 { |
32 | | -/**Time: O(n * 4^n / n^(3/2)) ~= n * Catalan numbers = n * (C(2n, n) - C(2n, n - 1)), |
33 | | - due to the size of the results is Catalan numbers, |
34 | | - and every way of evaluation is the length of the string, |
35 | | - so the time complexity is at most n * Catalan numbers. |
36 | | - Space: O(n * 4^n / n^(3/2)), the cache size of lookup is at most n * Catalan numbers.*/ |
| 32 | +publicstaticclassSolution1 { |
| 33 | +/**Time: O(n * 4^n / n^(3/2)) ~= n * Catalan numbers = n * (C(2n, n) - C(2n, n - 1)), |
| 34 | + due to the size of the results is Catalan numbers, |
| 35 | + and every way of evaluation is the length of the string, |
| 36 | + so the time complexity is at most n * Catalan numbers. |
| 37 | + Space: O(n * 4^n / n^(3/2)), the cache size of lookup is at most n * Catalan numbers.*/ |
37 | 38 |
|
38 | | -/**Credit: https://discuss.leetcode.com/topic/19901/a-recursive-java-solution-284-ms*/ |
39 | | -publicList<Integer>diffWaysToCompute(Stringinput) { |
40 | | -List<Integer>answer =newLinkedList<>(); |
41 | | -intlen =input.length(); |
42 | | -for (inti =0;i <len;i++) { |
43 | | -if (input.charAt(i) =='+' |
44 | | - ||input.charAt(i) =='-' |
45 | | - ||input.charAt(i) =='*') { |
46 | | -Stringpart1 =input.substring(0,i); |
47 | | -Stringpart2 =input.substring(i +1); |
48 | | -List<Integer>answer1 =diffWaysToCompute(part1); |
49 | | -List<Integer>answer2 =diffWaysToCompute(part2); |
50 | | -for (inta1 :answer1) { |
51 | | -for (inta2 :answer2) { |
52 | | -intresult =0; |
53 | | -switch (input.charAt(i)) { |
54 | | -case'+': |
55 | | -result =a1 +a2; |
56 | | -break; |
57 | | -case'-': |
58 | | -result =a1 -a2; |
59 | | -break; |
60 | | -case'*': |
61 | | -result =a1 *a2; |
62 | | -break; |
63 | | -default: |
64 | | -break; |
| 39 | +/** |
| 40 | + * Credit: https://discuss.leetcode.com/topic/19901/a-recursive-java-solution-284-ms |
| 41 | + */ |
| 42 | +publicList<Integer>diffWaysToCompute(Stringinput) { |
| 43 | +List<Integer>answer =newLinkedList<>(); |
| 44 | +intlen =input.length(); |
| 45 | +for (inti =0;i <len;i++) { |
| 46 | +if (input.charAt(i) =='+' |
| 47 | + ||input.charAt(i) =='-' |
| 48 | + ||input.charAt(i) =='*') { |
| 49 | +Stringpart1 =input.substring(0,i); |
| 50 | +Stringpart2 =input.substring(i +1); |
| 51 | +List<Integer>answer1 =diffWaysToCompute(part1); |
| 52 | +List<Integer>answer2 =diffWaysToCompute(part2); |
| 53 | +for (inta1 :answer1) { |
| 54 | +for (inta2 :answer2) { |
| 55 | +intresult =0; |
| 56 | +switch (input.charAt(i)) { |
| 57 | +case'+': |
| 58 | +result =a1 +a2; |
| 59 | +break; |
| 60 | +case'-': |
| 61 | +result =a1 -a2; |
| 62 | +break; |
| 63 | +case'*': |
| 64 | +result =a1 *a2; |
| 65 | +break; |
| 66 | +default: |
| 67 | +break; |
| 68 | + } |
| 69 | +answer.add(result); |
65 | 70 | } |
66 | | -answer.add(result); |
67 | 71 | } |
68 | 72 | } |
69 | 73 | } |
| 74 | +if (answer.size() ==0) { |
| 75 | +answer.add(Integer.valueOf(input)); |
| 76 | + } |
| 77 | +returnanswer; |
70 | 78 | } |
71 | | -if (answer.size() ==0) { |
72 | | -answer.add(Integer.valueOf(input)); |
73 | | - } |
74 | | -returnanswer; |
75 | 79 | } |
76 | | - |
77 | 80 | } |