43.Multiply Strings

Tags: [string_num], [multiply], [big_int]

Com: {fb}

Link: https://leetcode.com/problems/multiply-strings/#/description

Given two non-negative integersnum1andnum2represented as strings, return the product ofnum1andnum2.

Note:

1. The length of both num1and num2is < 110.
2. Both num1and num2contains only digits0-9.
3. Both num1and num2does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Better Solution:

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        if not num1 or not num2:
            return '0'

        result_sign = 1
        if num1[0] == '-':
            result_sign = -result_sign
            num1 = num1[1:]
        if num2[0] == '-':
            result_sign = -result_sign
            num2 = num2[1:]

        result = [0 for _ in xrange(len(num1) + len(num2))]
        for i in xrange(len(num1) - 1, -1, -1):
            for j in xrange(len(num2) -1, -1, -1):
                digit1 = ord(num1[i]) - ord('0')
                digit2 = ord(num2[j]) - ord('0')
                result[i + j + 1] += digit1 * digit2

        carry = 0
        for i in xrange(len(result) - 1, -1, -1):
            tmp = result[i] + carry
            carry = tmp / 10
            result[i] = tmp % 10

        # remove the leading 0s.
        target_index = -1
        for i in xrange(len(result)):
            if result[i] == 0:
                target_index = i
            else:
                break

        if target_index >= 0:
            result = result[target_index + 1:]

        if not result:
            return '0'

        return ''.join([str(x) for x in result])

Revelation:

• Knowledge: The length of the result of num1 * num2 must less than or equal to len(num1) + len(num2), for example, 99 * 99, the length of the result <= 4.
• The explanation of result[i + j + 1] = digit1 * digit2, please see the below picture:

Note:

• Time complexity = O(len(num1) * len(num2)).

Solution:

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        if not num1 or not num2:
            return '0'

        result_sign = 1
        if num1[0] == '-':
            result_sign = -result_sign
            num1 = num1[1:]
        if num2[0] == '-':
            result_sign = -result_sign
            num2 = num2[1:]

        short_n = num1 if len(num1) <= len(num2) else num2
        long_n = num1 if len(num1) > len(num2) else num2

        result = '0'
        for i in xrange(len(short_n) - 1, -1, -1):
            single_result = self.single_multiply(short_n[i], long_n)
            if single_result != '0':
                single_result += '0' * (len(short_n) - 1 - i)

            result = self.sum_str_nums(result, single_result)

        return result if result_sign > 0 else '-' + result

    def single_multiply(self, single_digit, num):
        result = []
        carry = 0
        digit = int(single_digit)
        for i in xrange(len(num) - 1, -1, -1):
            tmp = digit * int(num[i]) + carry
            if tmp >= 10:
                carry = tmp / 10
            else:
                carry = 0

            result.append(tmp % 10)

        if carry:
            result.append(carry)

        # remove the leading 0s.
        target_index = -1
        for i in xrange(len(result) - 1, -1, -1):
            if result[i] == 0:
                target_index = i
            else:
                break

        if target_index >= 0:
            result = result[:target_index]

        if not result:
            return '0'

        result.reverse()
        return ''.join([str(x) for x in result])

    def sum_str_nums(self, num1, num2):
        result = []
        carry = 0

        index1 = len(num1) - 1
        index2 = len(num2) - 1

        while index1 >= 0 and index2 >= 0:
            tmp = int(num1[index1]) + int(num2[index2]) + carry
            if tmp >= 10:
                carry = tmp / 10
            else:
                carry = 0

            result.append(tmp % 10)
            index1 -= 1
            index2 -= 1

        while index1 >= 0:
            tmp = int(num1[index1]) + carry
            if tmp >= 10:
                carry = tmp / 10
            else:
                carry = 0

            result.append(tmp % 10)
            index1 -= 1

        while index2 >= 0:
            tmp = int(num2[index2]) + carry
            if tmp >= 10:
                carry = tmp / 10
            else:
                carry = 0

            result.append(tmp % 10)
            index2 -= 1

        if carry:
            result.append(carry)

        if not result:
            return '0'

        result.reverse()
        return ''.join([str(x) for x in result])

Revelation:

• In the single_multiply function, we need to remove the leading 0s from the result. Because there exists the case: num1 = '9123', num2 = '0'.

Note:

• Time complexity = O(len(short_num) * len(long_num) * len(long_num)).