Here’s the question link on LeetCode 43. Multiply Strings:-
https://leetcode.com/problems/multiply-strings
Contents
Brute Force: Convert and Multiply O(m + n)
The simplest approach is to convert both strings into numbers, multiply them, and convert the result back into a string.
We can construct the numbers ourselves by multiplying the current number by 10 and adding the next digit.
But this fails the restrictions.
class Solution {
public:
string multiply(string num1, string num2) {
long long n1 = 0, n2 = 0;
for(char c : num1)
n1 = n1 * 10 + (c - '0');
for(char c : num2)
n2 = n2 * 10 + (c - '0');
long long product = n1 * n2;
if(product == 0)
return "0";
string ans = "";
while(product > 0) {
int digit = product % 10;
ans += ('0' + digit);
product /= 10;
}
reverse(ans.begin(), ans.end());
return ans;
}
};
Optimal: O(m × n)
We can simply simulate the multiplication we do on paper.
For example:
123
× 456
-------
738
6150
49200
-------
56088
Instead of creating separate rows and adding them, we can directly store the result in an array.
Let’s take 123 × 456.
The maximum size of the result can be m + n, where m and n are the lengths of the two strings.
So we create an array of size m + n, initially filled with zeroes.
vector<int> res(m + n, 0);
Now, multiply every digit of num1 with every digit of num2, starting from the right.
The important part is where we store the result.
For digits at indices i and j:
i + j + 1stores the current digit.i + jstores the carry.
int sum = (num1[i] - '0') * (num2[j] - '0') + res[i + j + 1];
res[i + j + 1] = sum % 10;
res[i + j] += sum / 10;
We use % 10 to get the current digit and / 10 to get the carry.
After processing all pairs of digits, we just convert the result array into a string, skipping any leading zeroes.
class Solution {
public:
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0")
return "0";
int m = num1.size();
int n = num2.size();
vector<int> res(m + n, 0);
for(int i = m - 1; i >= 0; i--) {
for(int j = n - 1; j >= 0; j--) {
int sum = (num1[i] - '0') * (num2[j] - '0') + res[i + j + 1];
res[i + j + 1] = sum % 10;
res[i + j] += sum / 10;
}
}
string ans = "";
int i = 0;
// Skip leading zeros
while(i < res.size() && res[i] == 0)
i++;
while(i < res.size()) {
ans += to_string(res[i]);
i++;
}
return ans;
}
};
43. Multiply Strings 43. Multiply Strings 43. Multiply Strings 43. Multiply Strings 43. Multiply Strings