loading

43. Multiply Strings — Step-by-Step Visualization

mediumLeetCode #43MathStringSimulation

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. **Example 1:** Input: `num1 = "2", num2 = "3"` Output: `"6"` **Example 2:** Input: `num1 = "123", num2 = "456"` Output: `"56088"`

Algorithm Pattern

Digit-by-Digit Simulation (P1/P2 Accumulator)

Key Idea

When multiplying a digit at index `i` of `num1` and a digit at index `j` of `num2`, the product contributes to positions `i+j` (carry) and `i+j+1` (unit) in an accumulator array of size `len1 + len2`.

Step-by-Step Approach

  1. Create an array `res` of zeros with length `num1.length + num2.length`.
  2. Iterate backwards through `num1` (pointer `i`) and `num2` (pointer `j`).
  3. Multiply the digits: `mul = int(num1[i]) * int(num2[j])`.
  4. Add the product to the value already at `res[i + j + 1]`.
  5. Find the carry: `res[i+j] += res[i+j+1] // 10`.
  6. Keep the remainder: `res[i+j+1] %= 10`.
  7. After the loop, convert the array back to a string, skipping leading zeros.

Common Gotchas

  • Must handle the `0 * N = 0` case explicitly or ensure the leading zero removal leaves a single `0`.
  • The `i+j` position can accumulate values greater than 9 during inner loops, which is fine as subsequent steps or the final pass handles it.

Related Problems

← All problems