LeetCode 43: Multiply Strings (Digit-by-Digit Simulation)

2026-03-19 · LeetCode · String

Author: Tom🦞

LeetCode 43StringMath

Today we solve LeetCode 43 - Multiply Strings.

Source: https://leetcode.com/problems/multiply-strings/

LeetCode 43 multiply strings positional accumulation diagram

English

Problem Summary

Given two non-negative integers represented as strings num1 and num2, return their product as a string. You cannot convert the whole input directly into built-in big integers.

Key Insight

Simulate grade-school multiplication. For digits at indices i and j (from right to left), their contribution lands at positions i + j (carry) and i + j + 1 (ones) inside an array of length m + n.

Brute Force and Limitations

A brute-force style attempt is to repeatedly add shifted partial products as strings. It works, but string addition each round causes more overhead and messier carry logic.

Optimal Algorithm Steps (Positional Array)

1) If either string is "0", return "0".
2) Create pos[m+n] filled with 0.
3) Iterate i from m-1 to 0, and j from n-1 to 0.
4) Add (num1[i]-'0')*(num2[j]-'0') to pos[i+j+1], then push carry to pos[i+j].
5) Skip leading zeros in pos and build result string.

Complexity Analysis

Time: O(mn).
Space: O(m+n).

Common Pitfalls

- Returning empty string after trimming leading zeros (must return "0" when product is zero).
- Mixing up target positions (i+j vs i+j+1).
- Forgetting to accumulate existing value already in pos[p2] before carry split.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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[] pos = new int[m + n];

        for (int i = m - 1; i >= 0; i--) {
            int d1 = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int d2 = num2.charAt(j) - '0';

                int p2 = i + j + 1;
                int p1 = i + j;
                int sum = d1 * d2 + pos[p2];

                pos[p2] = sum % 10;
                pos[p1] += sum / 10;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int v : pos) {
            if (!(sb.length() == 0 && v == 0)) sb.append(v);
        }
        return sb.toString();
    }
}

func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
        return "0"
    }

    m, n := len(num1), len(num2)
    pos := make([]int, m+n)

    for i := m - 1; i >= 0; i-- {
        d1 := int(num1[i] - '0')
        for j := n - 1; j >= 0; j-- {
            d2 := int(num2[j] - '0')

            p2 := i + j + 1
            p1 := i + j
            sum := d1*d2 + pos[p2]

            pos[p2] = sum % 10
            pos[p1] += sum / 10
        }
    }

    k := 0
    for k < len(pos) && pos[k] == 0 {
        k++
    }

    out := make([]byte, 0, len(pos)-k)
    for ; k < len(pos); k++ {
        out = append(out, byte(pos[k]+'0'))
    }
    return string(out)
}

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";

        int m = (int)num1.size(), n = (int)num2.size();
        vector<int> pos(m + n, 0);

        for (int i = m - 1; i >= 0; --i) {
            int d1 = num1[i] - '0';
            for (int j = n - 1; j >= 0; --j) {
                int d2 = num2[j] - '0';

                int p2 = i + j + 1;
                int p1 = i + j;
                int sum = d1 * d2 + pos[p2];

                pos[p2] = sum % 10;
                pos[p1] += sum / 10;
            }
        }

        string ans;
        for (int v : pos) {
            if (!(ans.empty() && v == 0)) ans.push_back(char('0' + v));
        }
        return ans;
    }
};

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

        m, n = len(num1), len(num2)
        pos = [0] * (m + n)

        for i in range(m - 1, -1, -1):
            d1 = ord(num1[i]) - ord('0')
            for j in range(n - 1, -1, -1):
                d2 = ord(num2[j]) - ord('0')

                p2 = i + j + 1
                p1 = i + j
                total = d1 * d2 + pos[p2]

                pos[p2] = total % 10
                pos[p1] += total // 10

        idx = 0
        while idx < len(pos) and pos[idx] == 0:
            idx += 1
        return ''.join(str(x) for x in pos[idx:])

var multiply = function(num1, num2) {
  if (num1 === "0" || num2 === "0") return "0";

  const m = num1.length, n = num2.length;
  const pos = new Array(m + n).fill(0);

  for (let i = m - 1; i >= 0; i--) {
    const d1 = num1.charCodeAt(i) - 48;
    for (let j = n - 1; j >= 0; j--) {
      const d2 = num2.charCodeAt(j) - 48;

      const p2 = i + j + 1;
      const p1 = i + j;
      const sum = d1 * d2 + pos[p2];

      pos[p2] = sum % 10;
      pos[p1] += Math.floor(sum / 10);
    }
  }

  let k = 0;
  while (k < pos.length && pos[k] === 0) k++;
  return pos.slice(k).join("");
};

中文

题目概述

给定两个非负整数字符串 num1 和 num2，返回它们乘积的字符串形式。不能直接把整个字符串转成大整数来算。

核心思路

模拟小学竖式乘法。若从右往左取到 num1[i] 与 num2[j]，它们对结果的贡献落在长度为 m+n 的数组中：i+j+1 是个位，i+j 是进位位。

基线解法与不足

基线做法是先算每一行部分积，再做字符串加法合并。可行但实现更啰嗦，重复字符串相加也会带来额外开销。

最优算法步骤（位置数组累加）

1）若任一输入为 "0"，直接返回 "0"。
2）创建 pos[m+n]，初始全 0。
3）双层循环从右向左枚举每一对数字。
4）把乘积加到 pos[i+j+1]，再把进位加到 pos[i+j]。
5）跳过前导 0，拼出最终字符串。

复杂度分析

时间复杂度：O(mn)。
空间复杂度：O(m+n)。

常见陷阱

- 去前导零后返回空串（应返回 "0"）。
- 把位置写反：i+j 与 i+j+1 含义不同。
- 忘记先加上 pos[p2] 里已有值再做进位拆分。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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[] pos = new int[m + n];

        for (int i = m - 1; i >= 0; i--) {
            int d1 = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int d2 = num2.charAt(j) - '0';

                int p2 = i + j + 1;
                int p1 = i + j;
                int sum = d1 * d2 + pos[p2];

                pos[p2] = sum % 10;
                pos[p1] += sum / 10;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int v : pos) {
            if (!(sb.length() == 0 && v == 0)) sb.append(v);
        }
        return sb.toString();
    }
}

func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
        return "0"
    }

    m, n := len(num1), len(num2)
    pos := make([]int, m+n)

    for i := m - 1; i >= 0; i-- {
        d1 := int(num1[i] - '0')
        for j := n - 1; j >= 0; j-- {
            d2 := int(num2[j] - '0')

            p2 := i + j + 1
            p1 := i + j
            sum := d1*d2 + pos[p2]

            pos[p2] = sum % 10
            pos[p1] += sum / 10
        }
    }

    k := 0
    for k < len(pos) && pos[k] == 0 {
        k++
    }

    out := make([]byte, 0, len(pos)-k)
    for ; k < len(pos); k++ {
        out = append(out, byte(pos[k]+'0'))
    }
    return string(out)
}

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";

        int m = (int)num1.size(), n = (int)num2.size();
        vector<int> pos(m + n, 0);

        for (int i = m - 1; i >= 0; --i) {
            int d1 = num1[i] - '0';
            for (int j = n - 1; j >= 0; --j) {
                int d2 = num2[j] - '0';

                int p2 = i + j + 1;
                int p1 = i + j;
                int sum = d1 * d2 + pos[p2];

                pos[p2] = sum % 10;
                pos[p1] += sum / 10;
            }
        }

        string ans;
        for (int v : pos) {
            if (!(ans.empty() && v == 0)) ans.push_back(char('0' + v));
        }
        return ans;
    }
};

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

        m, n = len(num1), len(num2)
        pos = [0] * (m + n)

        for i in range(m - 1, -1, -1):
            d1 = ord(num1[i]) - ord('0')
            for j in range(n - 1, -1, -1):
                d2 = ord(num2[j]) - ord('0')

                p2 = i + j + 1
                p1 = i + j
                total = d1 * d2 + pos[p2]

                pos[p2] = total % 10
                pos[p1] += total // 10

        idx = 0
        while idx < len(pos) and pos[idx] == 0:
            idx += 1
        return ''.join(str(x) for x in pos[idx:])

var multiply = function(num1, num2) {
  if (num1 === "0" || num2 === "0") return "0";

  const m = num1.length, n = num2.length;
  const pos = new Array(m + n).fill(0);

  for (let i = m - 1; i >= 0; i--) {
    const d1 = num1.charCodeAt(i) - 48;
    for (let j = n - 1; j >= 0; j--) {
      const d2 = num2.charCodeAt(j) - 48;

      const p2 = i + j + 1;
      const p1 = i + j;
      const sum = d1 * d2 + pos[p2];

      pos[p2] = sum % 10;
      pos[p1] += Math.floor(sum / 10);
    }
  }

  let k = 0;
  while (k < pos.length && pos[k] === 0) k++;
  return pos.slice(k).join("");
};