💬 Discord
Sign In
NeetCode #918LC-43MediumMath & GeometryNC 150NC 250
← Back to All Problems

#918 · #43 · Multiply Strings(字符串相乘)

📌 Problem Statement & Constraints

Given two non-negative integers num1 and num2 represented as strings, return their product as a string. You must not use any built-in big-integer library and must not convert the inputs to integers directly. Constraints: 1 <= num1.length, num2.length <= 200, both strings contain only digits and have no leading zeros except for the single character 0.

💡 Core Algorithmic Approaches

  1. Simulate grade-school long multiplication: multiply each digit of num1 by each digit of num2.
  2. Digit i of num1 (counted from the right) and digit j of num2 contribute to positions i + j and i + j + 1 of a result array of length m + n.
  3. Accumulate directly into that single array, carrying immediately so every cell stays a single digit -- no per-row partial products are stored.
  4. Strip the leading zeros at the end and join the digits into a string.

💻 Benchmark Python3 Implementation

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        m, n = len(num1), len(num2)
        res = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                mul = (ord(num1[i]) - ord("0")) * (ord(num2[j]) - ord("0"))
                p2 = i + j + 1               # units position of this product
                p1 = i + j                   # carry position
                total = mul + res[p2]
                res[p2] = total % 10
                res[p1] += total // 10
        i = 0
        while i < len(res) and res[i] == 0:
            i += 1                            # skip leading zeros
        return "".join(str(d) for d in res[i:])

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): every pair of digits is multiplied once.
💾 Space Complexity
O(m + n): the result array.

⚠️ Interview Pitfalls & Follow-ups

  • Calling int(num1) * int(num2): explicitly forbidden by the problem.
  • Carrying only after the inner loop finishes: carrying immediately into res[p1] keeps every cell a single digit; deferring requires a separate pass.
  • Allocating only m + n - 1 cells: the product can need m + n digits, so the extra slot is required.
  • Skipping the leading-zero strip: the array is right-aligned, so the front is padded with zeros.