[leetcode] Multiply Strings

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.

分析：

模拟手算乘法即可。分两部分：字符串的乘法，字符串的加法。

例如：

* 12

------------------

198

+ 99

------------------

297

 1 class Solution
 2 {
 3 public:
 4   string add(string num1, string num2)
 5   {
 6     string ret = "";
 7     int flag = 0, temp = 0;
 8     int i = num1.size() - 1, j = num2.size() - 1;
 9 
10     for(; i >= 0 || j >= 0; --i, --j)
11     {
12       if(i >= 0 && j >= 0)
13         temp = num1[i] - '0' + num2[j] - '0' + flag;
14       else if(i >= 0 && j < 0)
15         temp = num1[i] - '0' + flag;
16       else
17         temp = num2[j] - '0' + flag;
18 
19       flag = temp / 10;
20       temp = temp % 10;
21       ret.insert(ret.begin(), '0' + temp);
22     }
23 
24     if(flag == 1)
25       ret.insert(ret.begin(), '1');
26 
27     return ret;
28   }
29   
30 public:
31   string multiply(string num1, string num2)
32   {
33     if(num1 == "0" || num2 == "0")
34       return "0";
35 
36     string ret = "", str = "";
37     int i = 0, j = 0, temp = 0, flag = 0;
38 
39     for(j = num2.size()-1; j>=0; --j)
40     {
41       str = "";
42       flag = 0;
43       for(i = num1.size()-1; i>=0; --i)
44       {
45         temp = (num1[i] - '0') * (num2[j] - '0') + flag;
46         flag = temp / 10;
47         temp = temp % 10;
48         str.insert(str.begin(), temp + '0');
49       }
50       if(flag > 0)
51         str.insert(str.begin(), flag + '0');
52       
53       for(int k = j; k < num2.size()-1; k++)
54         str += "0";
55       
56       ret = add(str, ret);
57     }
58 
59     return ret;
60   }
61 };