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.
Example 1:
Input: num1 = "2", num2 = "3" Output: "6"
Example 2:
Input: num1 = "123", num2 = "456" Output: "56088"
Constraints:
1 <= num1.length, num2.length <= 200
num1
andnum2
consist of digits only.- Both
num1
andnum2
do not contain any leading zero, except the number0
itself.
Multiply Strings Solutions
✅Time: O(∣num1∣∣num2∣)
✅Space: um1∣+∣num2∣)
C++
class Solution {
public:
string multiply(string num1, string num2) {
string s(num1.length() + num2.length(), '0');
for (int i = num1.length() - 1; i >= 0; --i)
for (int j = num2.length() - 1; j >= 0; --j) {
const int mult = (num1[i] - '0') * (num2[j] - '0');
const int sum = mult + (s[i + j + 1] - '0');
s[i + j] += sum / 10;
s[i + j + 1] = '0' + sum % 10;
}
const int i = s.find_first_not_of('0');
return i == -1 ? "0" : s.substr(i);
}
};
Java
class Solution {
public String multiply(String num1, String num2) {
final int m = num1.length();
final int n = num2.length();
StringBuilder sb = new StringBuilder();
int[] pos = new int[m + n];
for (int i = m - 1; i >= 0; --i)
for (int j = n - 1; j >= 0; --j) {
final int multiply = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
final int sum = multiply + pos[i + j + 1];
pos[i + j] += sum / 10;
pos[i + j + 1] = sum % 10;
}
for (final int p : pos)
if (p > 0 || sb.length() > 0)
sb.append(p);
return sb.length() == 0 ? "0" : sb.toString();
}
}
Python
class Solution:
def multiply(self, num1: str, num2: str) -> str:
s = [0] * (len(num1) + len(num2))
for i in reversed(range(len(num1))):
for j in reversed(range(len(num2))):
mult = int(num1[i]) * int(num2[j])
summ = mult + s[i + j + 1]
s[i + j] += summ // 10
s[i + j + 1] = summ % 10
for i, c in enumerate(s):
if c != 0:
break
return ''.join(map(str, s[i:]))
Watch Tutorial
Checkout more Solutions here