Leetcode: Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

大整数的字符串乘法，我本来对字符串表示的大整数就不是太熟悉，至于溢出该怎么处理也是不大清楚，所以参考了别人的做法，然后自己凭着印象重做了一次

直接乘会溢出，所以每次都要两个single digit相乘，最大81，不会溢出。
比如385 * 97, 就是个位=5 * 7，十位=8 * 7 + 5 * 9 ，百位=3 * 7 + 8 * 9 …
可以每一位用一个Int表示，存在一个int[]里面。
这个数组最大长度是num1.len + num2.len，比如99 * 99，最大不会超过10000，所以4位就够了。
这种个位在后面的，不好做（10的0次方，可惜对应位的数组index不是0而是n-1），
所以干脆先把string reverse了代码就清晰好多。
最后结果前面的0要清掉。

这里面的方法比较巧妙，也比较典型，需要掌握。大整数的字符串乘法，不能直接乘，每次都要两个single digit相乘

再注意一下Corner Case, 31行，为什么要这么大费周折，因为如果input是“0”， “0”，结果也是“0”，而不是“”，28-29行只是为了删结果前面的0，而不是删成空String，如果结果是0，还得保留一个0

 1 public class Solution {
 2     public String multiply(String num1, String num2) {
 3         String st1 = (new StringBuffer(num1)).reverse().toString();
 4         String st2 = (new StringBuffer(num2)).reverse().toString();
 5         int[] result = new int[st1.length() + st2.length()];
 6         for (int i=0; i<st1.length(); i++) {
 7             int temp1 = (int)(st1.charAt(i) - '0');
 8             for (int j=0; j<st2.length(); j++) {
 9                 int temp2 = (int)(st2.charAt(j) - '0');
10                 result[i+j] += temp1 * temp2;
11             }
12         }
13         
14         StringBuffer res = new StringBuffer();
15         for (int k=0; k<result.length; k++) {
16             int digit = (int)(result[k] % 10);
17             int carry = (int)(result[k] / 10);
18             res.insert(0, digit);
19             if (k < result.length-1) {
20                 result[k+1] += carry;
21             }
22         }
23         
24         while (res.length()>1 && res.charAt(0) == '0') {
25             res.deleteCharAt(0);
26         }
27         return res.toString();
28     }
29 }

一开始我对溢出的理解不充分，并没有充分理解 “直接乘会溢出”的含义，于是写了个直接乘的code来测试：

1 public class Solution {
2     public String multiply(String num1, String num2) {
3         int n1 = Integer.parseInt(num1);
4         int n2 = Integer.parseInt(num2);
5         int num = n1 * n2;
6         return Integer.toString(num);
7     }
8 }

结果：java.lang.NumberFormatException: For input string: "6913259244"

Last executed input: "6913259244", "71103343"

这个 "6913259244"明显在Integer的有效范围之外（-2147483648 to 2147483647），因此直接乘是不适用的。更别提如果两个数相乘之后的积超过Integer_MAXVALUE呢。

而采取这种single digit相乘的方法，每次乘法最大都不会超过81，不会溢出