|
2 | 2 |
|
3 | 3 | publicclass_43 { |
4 | 4 |
|
5 | | -/**Inspired by https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation |
6 | | - * Basically, the rule we can find is that products of each two digits will land in this position in the final product: |
7 | | - * i+j and i+j+1*/ |
8 | | -publicStringmultiply(Stringnum1,Stringnum2) { |
9 | | -if (isZero(num1) ||isZero(num2)) { |
10 | | -return"0"; |
11 | | - } |
12 | | -int[]a1 =newint[num1.length()]; |
13 | | -int[]a2 =newint[num2.length()]; |
14 | | -int[]product =newint[num1.length() +num2.length()]; |
15 | | - |
16 | | -for (inti =a1.length -1;i >=0;i--) { |
17 | | -for (intj =a2.length -1;j >=0;j--) { |
18 | | -intthisProduct =Character.getNumericValue(num1.charAt(i)) *Character.getNumericValue(num2.charAt(j)); |
19 | | -product[i +j +1] +=thisProduct %10; |
20 | | -if (product[i +j +1] >=10) { |
21 | | -product[i +j +1] %=10; |
22 | | -product[i +j]++; |
| 5 | +publicstaticclassSolution1 { |
| 6 | +/** |
| 7 | + * Inspired by https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation |
| 8 | + * Basically, the rule we can find is that products of each two digits will land in this position in the final product: |
| 9 | + * i+j and i+j+1 |
| 10 | + */ |
| 11 | +publicStringmultiply(Stringnum1,Stringnum2) { |
| 12 | +if (isZero(num1) ||isZero(num2)) { |
| 13 | +return"0"; |
| 14 | + } |
| 15 | +int[]a1 =newint[num1.length()]; |
| 16 | +int[]a2 =newint[num2.length()]; |
| 17 | +int[]product =newint[num1.length() +num2.length()]; |
| 18 | + |
| 19 | +for (inti =a1.length -1;i >=0;i--) { |
| 20 | +for (intj =a2.length -1;j >=0;j--) { |
| 21 | +intthisProduct =Character.getNumericValue(num1.charAt(i)) *Character.getNumericValue(num2.charAt(j)); |
| 22 | +product[i +j +1] +=thisProduct %10; |
| 23 | +if (product[i +j +1] >=10) { |
| 24 | +product[i +j +1] %=10; |
| 25 | +product[i +j]++; |
| 26 | + } |
| 27 | +product[i +j] +=thisProduct /10; |
| 28 | +if (product[i +j] >=10) { |
| 29 | +product[i +j] %=10; |
| 30 | +product[i +j -1]++; |
| 31 | + } |
23 | 32 | } |
24 | | -product[i +j] +=thisProduct /10; |
25 | | -if (product[i +j] >=10) { |
26 | | -product[i +j] %=10; |
27 | | -product[i +j -1]++; |
| 33 | + } |
| 34 | + |
| 35 | +StringBuilderstringBuilder =newStringBuilder(); |
| 36 | +for (inti =0;i <product.length;i++) { |
| 37 | +if (i ==0 &&product[i] ==0) { |
| 38 | +continue; |
28 | 39 | } |
| 40 | +stringBuilder.append(product[i]); |
29 | 41 | } |
| 42 | +returnstringBuilder.toString(); |
30 | 43 | } |
31 | 44 |
|
32 | | -StringBuilderstringBuilder =newStringBuilder(); |
33 | | -for (inti =0;i <product.length;i++) { |
34 | | -if (i ==0 &&product[i] ==0) { |
35 | | -continue; |
| 45 | + |
| 46 | +privatebooleanisZero(Stringnum) { |
| 47 | +for (charc :num.toCharArray()) { |
| 48 | +if (c !='0') { |
| 49 | +returnfalse; |
| 50 | + } |
36 | 51 | } |
37 | | -stringBuilder.append(product[i]); |
| 52 | +returntrue; |
38 | 53 | } |
39 | | -returnstringBuilder.toString(); |
40 | 54 | } |
41 | 55 |
|
42 | | -privatebooleanisZero(Stringnum) { |
43 | | -for (charc :num.toCharArray()) { |
44 | | -if (c !='0') { |
45 | | -returnfalse; |
| 56 | +publicstaticclassSolution2 { |
| 57 | +/** |
| 58 | + * My completely original solution on 10/14/2021. |
| 59 | + * |
| 60 | + * Gist: just use string instead of integers for times variable, otherwise guaranteed to overflow/underflow! |
| 61 | + * Also: using a pen and paper to visualize how this works out helps a great deal! |
| 62 | + */ |
| 63 | +publicStringmultiply(Stringnum1,Stringnum2) { |
| 64 | +Stringprevious =""; |
| 65 | +Stringj =""; |
| 66 | +for (inti =num2.length() -1;i >=0;i--,j +="0") { |
| 67 | +Stringintermediate =multiplyBySingleDigit(num1,Character.getNumericValue(num2.charAt(i)),j); |
| 68 | +Stringresult =add(intermediate,previous); |
| 69 | +previous =result; |
| 70 | + } |
| 71 | +inti =0; |
| 72 | +for (;i <previous.length();i++) { |
| 73 | +if (previous.charAt(i) !='0') { |
| 74 | +break; |
| 75 | + } |
| 76 | + } |
| 77 | +returni ==previous.length() ?"0" :previous.substring(i); |
| 78 | + } |
| 79 | + |
| 80 | +privateStringadd(Stringnum1,Stringnum2) { |
| 81 | +inti =num1.length() -1; |
| 82 | +intj =num2.length() -1; |
| 83 | +intcarry =0; |
| 84 | +StringBuildersb =newStringBuilder(); |
| 85 | +while (i >=0 ||j >=0) { |
| 86 | +intsum =carry; |
| 87 | +if (i >=0) { |
| 88 | +sum +=Character.getNumericValue(num1.charAt(i)); |
| 89 | + } |
| 90 | +if (j >=0) { |
| 91 | +sum +=Character.getNumericValue(num2.charAt(j)); |
| 92 | + } |
| 93 | +sb.append(sum %10); |
| 94 | +carry =sum /10; |
| 95 | +i--; |
| 96 | +j--; |
| 97 | + } |
| 98 | +if (carry >0) { |
| 99 | +sb.append(carry); |
| 100 | + } |
| 101 | +returnsb.reverse().toString(); |
| 102 | + } |
| 103 | + |
| 104 | +privateStringmultiplyBySingleDigit(Stringnum,intmultiplier,Stringtimes) { |
| 105 | +if (multiplier ==0) { |
| 106 | +return"0"; |
| 107 | + } |
| 108 | +StringBuildersb =newStringBuilder(); |
| 109 | +intcarry =0; |
| 110 | +for (inti =num.length() -1;i >=0;i--) { |
| 111 | +intval =Character.getNumericValue(num.charAt(i)); |
| 112 | +intproduct =val *multiplier; |
| 113 | +product +=carry; |
| 114 | +sb.append(product %10); |
| 115 | +carry =product /10; |
| 116 | + } |
| 117 | +if (carry >0) { |
| 118 | +sb.append(carry); |
46 | 119 | } |
| 120 | +returnsb.reverse() +times; |
47 | 121 | } |
48 | | -returntrue; |
49 | 122 | } |
50 | 123 |
|
51 | 124 | } |