43. Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
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
| class Solution {
public:
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0")
return "0";
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
vector<int> ans(num1.length() + num2.length(), 0);
for(int i = 0; i < num1.length(); i++) {
if(num1[i] == '0') continue;
int carry = 0;
for(int j = 0; j < num2.length(); j++) {
ans[i + j] += (num1[i] & 0b1111) * (num2[j] & 0b1111) + carry;
carry = ans[i + j] / 10;
ans[i + j] %= 10;
}
if(carry) {
ans[i + num2.length()] += carry;
}
}
while(!ans.back()) {
ans.pop_back();
}
stringstream ss;
for(int i = ans.size() - 1; i >= 0; i--)
ss<<ans[i];
return ss.str();
}
};
|
1
2
3
4
5
6
7
8
9
10
| import java.math.BigInteger;
class Solution {
public String multiply(String num1, String num2) {
BigInteger b1 = new BigInteger(num1);
BigInteger b2 = new BigInteger(num2);
return b1.multiply(b2).toString();
}
}
|
