leetcode43

Posted on | In

43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

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

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

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Idea

Simply thinking, decompose the multiplication into multiply num1 with each bit of num2 and add them together.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution:
    """
    @param num1: a non-negative integers
    @param num2: a non-negative integers
    @return: return product of num1 and num2
    """
    def __init__(self):
        self.d = {str(i): i for i in range(0, 10)}
        self.s = {i: str(i) for i in range(0, 10)}
	
    def multiply(self, num1, num2):
        # num1 is smaller number
        if num1 == '0' or num2 == '0':
            return '0'
        
        total_sum = "0"
        for i, figure in enumerate(num1[::-1]):
            term = self.single_multiply(num2, figure) + "0" * i
            total_sum = self.add(term, total_sum)
        return total_sum
            
    def single_multiply(self, num, bit):
        idx = len(num) - 1
        b = self.d[bit]
        carry = 0
        cur = 0
        res = ''
        while idx >= 0:
            n1 = self.d[num[idx]]
            cur = (n1 * b + carry) % 10
            carry = (n1 * b + carry) / 10
            res = self.s[cur] + res
            idx -= 1
        
        if carry > 0:
            res = self.s[carry] + res
        return res
    
    def add(self, num1, num2):
        if not num1:
            num1 = '0'
        if not num2:
            num2 = '0'

        idx1 = len(num1) - 1
        idx2 = len(num2) - 1 
        
        res = ''
        cur = 0
        carry = 0
        while idx1 >= 0 or idx2 >= 0:
            n1 = self.d[num1[idx1]] if idx1 >= 0 else 0
            n2 = self.d[num2[idx2]] if idx2 >= 0 else 0
            cur = (n1 + n2 + carry) % 10
            carry = (n1 + n2 + carry) / 10
            res = self.s[cur] + res
            idx1 -= 1
            idx2 -= 1
        if carry == 1:
            res = '1' + res

        return res

Python

1
2
3
4
5
a = [1, 2, 3, 4]
print(a[len(a) - 1::-1])
print(a[::-1]) # omission
[4, 3, 2, 1]
[4, 3, 2, 1]