LeetCode 43 · Medium · Math & Geometry

Multiply Strings

Two non-negative integers arrive as digit strings. Return their product as a string, without converting either one to a built-in integer.

O(m · n)time
O(m + n)space
res[i1 + i2]where each digit product lands

digits only · 1–6 digits each · no leading zero (except "0" itself)

digit products rows: num1 · columns: num2 · the small number is i1 + i2, the res slot it adds into

res written most significant first; slot labels are the reversed index i1 + i2

public String multiply(String num1, String num2) { if (num1.equals("0") || num2.equals("0")) { return "0"; } int[] res = new int[num1.length() + num2.length()]; num1 = new StringBuilder(num1).reverse().toString(); num2 = new StringBuilder(num2).reverse().toString(); for (int i1 = 0; i1 < num1.length(); i1++) { for (int i2 = 0; i2 < num2.length(); i2++) { int d1 = num1.charAt(i1) - '0'; int d2 = num2.charAt(i2) - '0'; int digit = d1 * d2; res[i1 + i2] += digit; res[i1 + i2 + 1] += res[i1 + i2] / 10; res[i1 + i2] = res[i1 + i2] % 10; } } int beg = res.length - 1; while (beg >= 0 && res[beg] == 0) { beg--; } StringBuilder sb = new StringBuilder(); for (int p = beg; p >= 0; p--) { sb.append(res[p]); } return sb.toString();}
i1, i2
—
digit
—
res (reversed)
—

Why it works

  1. Schoolbook with partial rows: multiply num1 by each digit of num2, shift, then add the partial results as strings. Also O(m · n), but with m extra strings and a separate big addition.
  2. Place value decides the slot: with both strings reversed, digit i1 is worth 10i1 and digit i2 is worth 10i2, so their product belongs at 10i1+i2: res[i1 + i2]. Every cell on one anti-diagonal of the grid shares a slot.
  3. Carry immediately: after adding a product, keep res[i1 + i2] % 10 and push the tens into the next slot. A slot can briefly exceed 9, but it is normalised the next time a product lands there or is carried on later.
  4. Size: an m-digit number times an n-digit number has at most m + n digits, so the array never overflows. m · n products: O(m · n) time, O(m + n) space.
  5. Pitfall: leading zeros. 25 × 4 = 100 fits in 3 of the 4 slots; skip the zeros at the front, and handle "0" up front or the answer would be an empty string.
  6. Related: Add Strings and Plus One use the same carry; Karatsuba multiplies huge numbers in about O(n1.58).