Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product as a string. Do not use built-in BigInteger.

Example 1

Input: "2" * "3" → Output: "6"

Example 2

Input: "123" * "456" → Output: "56088"

Solution Approach

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.

Java

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)