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.
Examples
Constraints
1 <= num1.length, num2.length <= 200num1 and num2 consist of digits only.Both num1 and num2 do not contain any leading zero, except the number "0" itself.
Schoolbook Multiplication
Approach
We simulate the standard manual multiplication process. If `num1` has length `m` and `num2` has length `n`, their product can have at most `m + n` digits. We create an array `res` of size `m + n` to store the intermediate results. We iterate backwards through `num1` and `num2`. When we multiply `num1[i]` and `num2[j]`, the result contributes to `res[i + j + 1]` (the current position) and `res[i + j]` (the carry position). We add the product to `res[i + j + 1]`, handle the carry, and update `res[i + j]`. Finally, we convert the `res` array to a string, making sure to skip any leading zeros.
Complexity Analysis
Time complexity is O(m * n) where m and n are the lengths of the two strings. Space complexity is O(m + n) for the result array.
class Solution { public String multiply(String num1, String num2) { if ("0".equals(num1) || "0".equals(num2)) return "0"; int m = num1.length(); int n = num2.length(); int[] res = new int[m + n]; for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); // Add to the current position (which might already have carry from previous steps) int sum = mul + res[i + j + 1]; res[i + j + 1] = sum % 10; // Current digit res[i + j] += sum / 10; // Carry to next digit } } StringBuilder sb = new StringBuilder(); for (int val : res) { // Skip leading zeros if (!(sb.length() == 0 && val == 0)) { sb.append(val); } } return sb.length() == 0 ? "0" : sb.toString(); }}