43. Multiply Strings

Problem

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.

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

Example 1:

Input: num1 = “2”, num2 = “3”
Output: “6”

Example 2:

Input: num1 = “123”, num2 = “456”
Output: “56088”

Constraints:

1 <= num1.length, num2.length <= 200
num1 and num2 consist of digits only.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Test Cases

1 2	class Solution: def multiply(self, num1: str, num2: str) -> str:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('num1, num2, expected', [
    ('2', '3', '6'),
    ('123', '456', '56088'),

    ("123456789", "987654321", "121932631112635269"),
    ('9', '9', '81'),
    ('99', '99', '9801'),
    ('1000', '1000', '1000000'),
])

@pytest.mark.parametrize('sol', [Solution()])
class Test:
    def test_solution(self, sol, num1, num2, expected):
        assert sol.multiply(num1, num2) == expected

Thoughts

直接像乘法竖式计算那样逐位相乘即可。注意一个 m 位数和一个 n 位数相乘（不考虑有 0 的情况），乘积要么是 m + n 位数，要么是 m + n - 1 位数。

时间复杂度 O(m * n)，空间复杂度 O(m + n)。

Code

solution.py

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

        digits1 = [int(d) for d in num1]
        digits2 = [int(d) for d in num2]
        res = [0] * (len(num1) + len(num2))
        for i, d1 in enumerate(digits1):
            if d1 == 0: continue
            for j, d2 in enumerate(digits2):
                if d2 > 0:
                    res[i+j+1] += d1 * d2

        for i in range(len(res) - 1, 0, -1): # res[0] is for final carry, it is 0 now.
            c, res[i] = divmod(res[i], 10)
            res[i-1] += c

        i = 0 if res[0] else 1
        return ''.join(str(d) for d in res[i:])

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。