Given two non-negative integers num1 and num2 represented as strings, return the product as a string. Do not use built-in BigInteger.
Input: "2" * "3" → Output: "6"Input: "123" * "456" → Output: "56088"
Simulate grade-school multiplication. Result[i+j+1] += num1[i]*num2[j]. Handle carry. Skip leading zeros.
- Initialize result array of size m+n.
- For i from m-1 to 0: for j from n-1 to 0: mul = (num1[i]-0)*(num2[j]-0); result[i+j+1] += mul; carry to result[i+j].
- Convert to string, skip leading zeros.
class Solution {
public String multiply(String num1, String num2) {
int m = num1.length(), n = num2.length();
int[] result = 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');
result[i+j+1] += mul;
result[i+j] += result[i+j+1] / 10;
result[i+j+1] %= 10;
}
}
StringBuilder sb = new StringBuilder();
for (int v : result) if (!(sb.length() == 0 && v == 0)) sb.append(v);
return sb.length() == 0 ? "0" : sb.toString();
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(M+N)