C++ O(mn) 8ms solution

• ``````class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
int size1 = num1.size(), size2 = num2.size();
string ans(size1 + size2, '0');
reverse(num1); reverse(num2);
for (int i = 0; i < size1; ++i){
int carry = 0, digit1 = num1[i] - '0';
for (int j = 0; j < size2; ++j){
int digit2 = num2[j] - '0', res = ans[i+j] - '0', product = digit1 * digit2;
int sum = res + carry + product;
res = sum % 10;
carry = sum / 10;
ans[i+j] = '0' + res;
}
int digit = ans[i + size2] - '0';
if (digit + carry < 10) ans[i + size2] = '0' + digit + carry;
else{
ans[i + size2] = '0' + (digit + carry) % 10;
ans[i + size2 + 1] = '1';
}
}
reverse(ans);
int i = 0;
while (ans[i] == '0') ++i;
return ans.substr(i, size1 + size2);
}

void reverse(string& s){
int n = s.size();
int step = 0, i = 0, j = n-1;
while (step < n / 2){
s[i] ^= s[j] ^= s[i] ^= s[j];
++i; --j;
++step;
}
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.