-
Notifications
You must be signed in to change notification settings - Fork 0
/
043_Multiply Strings
35 lines (31 loc) · 1.01 KB
/
043_Multiply Strings
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//the intergers are too big to compute in ordinary arithmetrics.
class Solution {
public:
string multiply(string num1, string num2) {
int l1 = num1.length(), l2 = num2.length();
if( l1 ==0 || l2==0) return "0";
vector<int> reverse(l1+l2, 0);
for (int i = 0; i < l1; i++)
{
int digit1 = num1[l1 - i - 1] - '0';
int carry = 0;
for (int j = 0; j < l2; j++)
{
int digit2 = num2[l2 - j - 1] - '0';
int sum = digit1 * digit2 + reverse[i+j] + carry;
carry = sum/10;
reverse[i+j] = sum%10;
}
if (carry>0) reverse[i + l2] += carry;
}
int start = l1 + l2 -1;
while( start > -1 && reverse[start]==0) start--;
if(start == -1) return "0";
string ans="";
for (int i = start; i >= 0; i-- )
{
ans += (char)(reverse[i]+'0');
}
return ans;
}
};