[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.

num1或num2为零需要单独考虑，否则结果会出现类似0000的情况。

```class Solution {
public:
string multiply(string num1, string num2) {
int i = 0;
string re;
if(num1 == "0" || num2 == "0"){
return string("0");
}
while(i < num2.size()){
int digit = num2[i++] - '0';
string thisRe = multiplyNum(num1, digit);
if(re.empty()){
re = thisRe;
}
else{
re.push_back('0');
re = sum(re, thisRe);
}
}
return re;
}
string multiplyNum(string num1, int n){
string re;
int carry = 0;
for(string::iterator it = num1.end() - 1; it >= num1.begin(); it--){
int digit = *it - '0';
int thisRe = digit * n + carry;
carry = 0;
while(thisRe >= 10){
thisRe -= 10;
carry++;
}
re.insert(re.begin(), (char)(thisRe + '0'));
}
if(carry != 0){
re.insert(re.begin(), (char)(carry + '0'));
}
return re;
}
string sum(string num1, string num2){
int carry = 0;
int i = num1.size() - 1;
int j = num2.size() - 1;
string re;
while(i >= 0 || j >= 0){
int a = i >= 0? num1[i--] - '0': 0;
int b = j >= 0? num2[j--] - '0': 0;
int sum = a + b + carry;
carry = 0;
while(sum >= 10){
sum -= 10;
carry++;
}
re.insert(re.begin(), (char)(sum + '0'));
}
if(carry > 0){
re.insert(re.begin(), (char)(carry + '0'));
carry = 0;
}
return re;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.