41. Multiply Strings

The product of digit i of num1 and digit j of num2 lands in result positions i+j (carry) and i+j+1 (ones). Accumulate all digit-pair products into a result array, then read it off.

The position rule

For num1[i] and num2[j], their product contributes to two slots of a result array of length m + n:

• i + j + 1 holds the ones digit,
• i + j receives the carry.

Algorithm

res = [0] * (m + n)
for i from m-1 down to 0:
    for j from n-1 down to 0:
        mul = (num1[i]) * (num2[j])
        total = mul + res[i+j+1]
        res[i+j+1] = total % 10
        res[i+j]  += total // 10
skip leading zeros; join res

Worked example

"123" × "456": every digit pair is placed by the i+j rule and carried, producing res = [0,5,6,0,8,8] → strip the leading 0 → "56088".

Complexity

• Time: O(m·n).
• Space: O(m + n).

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        int m = num1.length(), 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');
                int p1 = i + j, p2 = i + j + 1;
                int total = mul + res[p2];
                res[p2] = total % 10;
                res[p1] += total / 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int d : res) {
            if (!(sb.length() == 0 && d == 0)) sb.append(d);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}