43. Multiply Strings

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: num1 = "2", num2 = "3" Output: "6"

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.

Solution Approach

The solution simulates the multiplication process digit by digit, similar to how it’s done manually, by reversing the strings, calculating partial products, and then summing and adjusting for carries before converting the result back to a string.

Algorithm

1. Reverse and Multiply: Reverse both strings and multiply each digit of num1 with each digit of num2, storing the results in a result array that accounts for the position of each digit.
2. Handle Carries: After each multiplication, update the result array with the carry value, ensuring each position in the array has a single digit.
3. Construct the Result: Reverse the result array back to the correct order, remove any leading zeros, and join the digits into a final string to represent the product.

Implement

    class Solution:
        def multiply(self, num1: str, num2: str) -> str:
            if "0" in [num1, num2]:
                return "0"
            
            res = [0] * (len(num1) + len(num2))
            num1, num2 = num1[::-1], num2[::-1]

            for i1 in range(len(num1)):
                for i2 in range(len(num2)):
                    digit = int(num1[i1]) * int(num2[i2])
                    res[i1 + i2] += digit
                    res[i1 + i2 + 1] += (res[i1 + i2] // 10)
                    res[i1 + i2] = res[i1 + i2] % 10
            res, beg = res[::-1], 0
            while beg < len(res) and res[beg] == 0:
                beg += 1

            res = map(str, res[beg:])
            return "".join(res)

 

    
    

Twitter  facebook  Email