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.

思路：

大整数乘法，转换成大整数加法来算。

代码：

 1     string add(string num1, string num2){
 2         int l1 = num1.length(), l2 = num2.length();
 3         if(l1 > l2)
 4             return add(num2, num1);
 5         int i;
 6         int carry = 0;
 7         string result = "";
 8         for(i = l1-1; i >= 0; i--){
 9             int tmp = num1[i] - '0' + num2[i+l2-l1] - '0' + carry;
10             result = (char)(tmp%10 + '0') + result;
11             carry = tmp/10;
12         }
13         for(i = l2-l1-1; i >= 0; i--){
14             int tmp = num2[i] - '0' + carry;
15             result = (char)(tmp%10 + '0') + result;
16             carry = tmp/10;
17         }
18         if(carry > 0)
19             result = (char)(carry + '0') + result;
20         return result;
21     }
22     string multiply(string num1, string num2) {
23         // IMPORTANT: Please reset any member data you declared, as
24         // the same Solution instance will be reused for each test case.
25         int l1 = num1.length(), l2 = num2.length();
26         if(l1 < l2)
27             return multiply(num2, num1);
28         if(l1 == 0)
29             return "";
30         if(l1 == 1){
31             if(num1[0] == '0')
32                 return "0";
33             if(num1[0] == '1')
34                 return num2;
35         }
36         int i,j;
37         string result = "";
38         for(i = l2-1; i >= 0; i--){
39             string tstring = "";
40             int carry = 0;
41             if(num2[i] == '0')
42                 continue;
43             for(j = l1-1; j >= 0; j--){
44                 int tmp = (num2[i]-'0')*(num1[j]-'0') + carry;
45                 tstring = (char)(tmp%10 + '0') + tstring;
46                 carry = tmp/10;
47             }
48             if(carry > 0)
49                 tstring = (char)(carry + '0') + tstring;
50             for(int k = 0; k < l2-i-1; k++)
51                 tstring += '0';
52             if(result == "")
53                 result = tstring;
54             else
55                 result = add(result, tstring);
56         }
57         if(result == "")
58             return "0";
59         return result;
60     }

第一遍的方法比较麻烦，其实还可以先用int数组存中间结果，然后再转换为字符串。代码如下：

 1     string multiply(string num1, string num2) {
 2         if(num1 == "0" || num2 == "0")
 3             return "0";
 4         int l1 = num1.length(), l2 = num2.length();
 5         int *n1 = new int[l1], *n2 = new int[l2], *r = new int[l1+l2];
 6         int i,j;
 7         string result = "";
 8         for(i = 0; i < l1; i++)
 9             n1[i] = num1[i]-'0';
10         for(i = 0; i < l2; i++)
11             n2[i] = num2[i]-'0';
12         memset(r, 0, sizeof(int)*(l1+l2));
13         for(i = 0; i < l1; i++){
14             for(j = 0; j < l2; j++){
15                 r[i+j+1] += n1[i]*n2[j];
16             }
17         }
18         for(i = l1+l2-1; i >= 1; i--){
19             result = (char)(r[i]%10+'0')+result;
20             r[i-1] += (r[i]/10);
21         }
22         if(r[0] > 0)
23             result = (char)(r[0]+'0')+result;
24         return result;
25     }