Can I use built-in integer conversion for Multiply Strings?

No, using direct integer conversion or BigInteger libraries violates the problem constraints; the solution must simulate multiplication purely with strings.

What is the recommended approach to handle carries in Multiply Strings?

Use a result array where each index accumulates products and carry values, updating sequentially to maintain correct single-digit positions.

How does reversing input strings help in the Multiply Strings solution?

Reversing allows starting multiplication from the least significant digit, aligning with manual column multiplication and simplifying carry propagation.

What should be returned if one of the inputs is "0"?

If either input is "0", the correct result is simply "0" since any number multiplied by zero is zero.

Can this approach handle very long strings up to 200 digits?

Yes, the O(M * N) time complexity and O(M + N) space complexity are designed to handle the maximum input lengths efficiently.

#43

Medium

auto_awesome数学·string

LeetCode 题解工作台

字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2 ，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。示例 1: 输入: num1 = "2", num2 = "3" 输出: "6" 示例 2…

数学字符串模拟

题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示：

1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。

lightbulb

解题思路

方法一：数学乘法模拟

假设 $num1$ 和 $num2$ 的长度分别为 $m$ 和 $n$ ，则它们的乘积的长度最多为 $m + n$ 。

证明如下：

如果 $num1$ 和 $num2$ 都取最小值，那么它们的乘积为 ${10}^{m - 1} \times {10}^{n - 1} = {10}^{m + n - 2}$ ，长度为 $m + n - 1$ 。
如果 $num1$ 和 $num2$ 都取最大值，那么它们的乘积为 $({10}^m - 1) \times ({10}^n - 1) = {10}^{m + n} - {10}^m - {10}^n + 1$ ，长度为 $m + n$ 。

因此，我们可以申请一个长度为 $m + n$ 的数组，用于存储乘积的每一位。

从低位到高位，依次计算乘积的每一位，最后将数组转换为字符串即可。

注意判断最高位是否为 $0$ ，如果是，则去掉。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m + n)$ 。其中 $m$ 和 $n$ 分别为 $num1$ 和 $num2$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        m, n = len(num1), len(num2)
        arr = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            a = int(num1[i])
            for j in range(n - 1, -1, -1):
                b = int(num2[j])
                arr[i + j + 1] += a * b
        for i in range(m + n - 1, 0, -1):
            arr[i - 1] += arr[i] // 10
            arr[i] %= 10
        i = 0 if arr[0] else 1
        return "".join(str(x) for x in arr[i:])

speed

复杂度分析

指标	值
时间	complexity is O(M * N) because each digit in num1 multiplies with each digit in num2. Space complexity is O(M + N) to store intermediate results in the result array representing the product of M and N digit numbers.
空间	O(M + N)

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate handles carry propagation correctly in a digit-by-digit simulation.
question_mark
Watch for attempts to convert strings directly to integers, which violates constraints.
question_mark
Assess whether the candidate efficiently manages the result array without unnecessary string concatenations.

warning

常见陷阱

外企场景

error
Failing to reverse the input strings before multiplying can misalign digits and produce incorrect results.
error
Ignoring carry propagation leads to digits exceeding 9 and incorrect final products.
error
Returning partial results or failing to remove leading zeros may cause format errors in the output string.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Multiply Strings using recursive divide-and-conquer instead of iterative simulation for large digit inputs.
arrow_right_alt
Implement multiplication with memory optimization to reduce the intermediate array size to a minimal representation.
arrow_right_alt
Handle negative numbers represented as strings, extending the simulation to include sign management.

help

常见问题

外企场景

继续练习

#67 二进制求和 #412 Fizz Buzz #415 字符串相加