Multiply Strings

Desicription

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

  1. The length of both num1 and num2 is < 110.
  2. Both num1 and num2 contains only digits 0-9.
  3. Both num1 and num2 does not contain any leading zero.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
string multiply(string num1, string num2) {
string res(num1.size() + num2.size(), '0');
for(int i = num1.size()-1; i >= 0; i--){
int carry = 0;
for(int j = num2.size()-1; j >= 0; j--){
int tmp = res[i+j+1] - '0' + (num1[i] - '0') * (num2[j] - '0') + carry;
res[i+j+1] = tmp % 10 + '0';
carry = tmp / 10;
}
res[i] += carry;
}
size_t index = res.find_first_not_of("0");
if(index != string::npos)
return res.substr(index);
return "0";
}
};