menu

[LeetCode] 043. Multiply Strings

Problem (Medium)

043. 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:

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

Approach 1: (My Solution)

Idea

  • Make two dictionaries:
      1. Adding dict (i.e. (‘1’, ‘1’): 2, (‘4’, ‘5’): 9, …);
      1. Multiplying dict (i.e. (‘0’, ‘8’): 0, (‘6’, ‘7’): 42, …);
  • Follow the rules when we do multiplication by hand, when using simple adding or multiplying, check the dictionaries above.

Solution

class Solution1:
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        # Adding, multiplication dictionaries:
        add = {tuple(sorted([str(i), str(j)])):i+j for i in range(10)  for j in range(10)}
        multi = {tuple(sorted([str(i), str(j)])):i*j for i in range(10) for j in range(10)}

        # get trailing zeros in both numbers
        if any((num1 == '0', num2 == '0')):
            return '0'
        zeros = ''
        zeros += '0' * (len(num1) - len(num1.rstrip('0')))
        zeros += '0' * (len(num2) - len(num2.rstrip('0')))

        # Do the multiplication
        res, num1, num2 = 0, num1.rstrip('0'), num2.rstrip('0')
        for i, b in enumerate(num2[::-1]):
            tmp, inc = 0, 0
            for j, a in enumerate(num1[::-1]):
                tmp += pow(10, j) * (multi[tuple(sorted([a, b]))] % 10 + inc)
                inc = multi[tuple(sorted([a, b]))] // 10
            if inc:
                tmp += pow(10, len(num1)) * inc
            res += pow(10, i) * tmp
        return str(res) + zeros

Complexity

  • Time: $O(mn)$
  • Space: $O()$?



KF

Comments