Problem
Given two non-negative integersnum1 and num2 represented as strings, return their product as a string.
The input numbers can be very large, so directly converting them to an integer type may cause overflow.
Example(s)
Example 1
Input
num1 = "2"
num2 = "3"Output
"6"Example 2
Input
num1 = "123"
num2 = "456"Output
"56088"Solution
Each digit ofnum1 is multiplied with each digit of num2, similar to manual multiplication.
The intermediate results are stored in an integer array, where position
i + j represents the place value of multiplying digits at positions i and j.
After all multiplications, handle the carry values and build the final result while removing leading zeros.
class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
int[] result = new int[num1.length() + num2.length()];
for (int i = num1.length() - 1; i >= 0; i--) {
for (int j = num2.length() - 1; j >= 0; j--) {
int digit1 = num1.charAt(i) - '0';
int digit2 = num2.charAt(j) - '0';
int product = digit1 * digit2;
int position = i + j + 1;
int sum = product + result[position];
result[position] = sum % 10;
result[position - 1] += sum / 10;
}
}
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < result.length && result[i] == 0) {
i++;
}
while (i < result.length) {
sb.append(result[i++]);
}
return sb.toString();
}
}Complexity
The time complexity is O(m × n), wherem and n are the lengths of the two input strings. The space complexity is O(m + n) for the result array.