Python solution with detailed explanation


  • 0
    G

    Solution with discussion https://discuss.leetcode.com/topic/77972/python-solution-with-detailed-explanation

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

    Brute Force Solution

    • Multiple digit by digit and use add strings to form the answer. This results in TLE.
    • We need to use addStrings since overflow can happen.
    class Solution(object):
        def addStrings(self, num1, num2):
            """
            :type num1: str
            :type num2: str
            :rtype: str
            """
            N, M = len(num1), len(num2)
            i,j = N-1, M-1
            result, carry = [], 0
            while i >= 0 or j >= 0:
                if i >= 0 and j >= 0:
                    s = int(num1[i]) + int(num2[j]) + carry
                    s, carry = s%10, s//10
                    result.append(str(s))
                    i,j= i-1, j-1 
                elif i >= 0:
                    s = int(num1[i]) + carry
                    s, carry = s%10, s//10
                    result.append(str(s))
                    i= i-1 
                elif j >= 0:
                    s = int(num2[j]) + carry
                    s, carry = s%10, s//10
                    result.append(str(s))
                    j = j-1 
            if carry:
                result.append(str(carry))
            result.reverse()
            return "".join(result)
            
        def mult(self, s, digit):
            factor, result, prev = 0, 0, "0"
            for i in range(len(s)-1, -1, -1):
                result = self.addStrings(str(int(digit)*int(s[i])) + "".join(["0"]*factor), prev)
                prev = result
                factor = factor + 1
            return result
        
        def multiply(self, num1, num2):
            """
            :type num1: str
            :type num2: str
            :rtype: str
            """
            factor, result, prev = 0, 0, "0"        
            for i in range(len(num1)-1, -1, -1):
                result = self.addStrings(self.mult(num2, num1[i]) + "".join(["0"]*factor), prev)
                prev = result
                factor = factor + 1
            res = result.lstrip("0")
            return "0" if not res else res
    

    Optimized Solution

    • Fist determine how many digits in final answer. 99999 will have at max 5 digits. For n1 and n2, max size is len(n1)+len(n2).
    • How do we multiply numbers using hand? We want a method by which we can directly update the result incrementally. Here is an an example: https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation
    • Reverse the inputs. The index in the reversed input should help you in determining the index of the resultant product.
    • Given 2 digits, the result be atmost 2 digits. The result LSD will be placed at index i+j. MSD will be placed i+j+1. Now there could be a previous value at index i+j - that needs to be added to the product of two digits. Then we have to update indices i+j and i+j+1. Note there will be no carry generated at index i+j+1 since the maximum product can only be 81 and 8+1 =9
    • Remove the unwanted zeroes. For that, try an example and be careful how we remove the zeroes.
    • Here is a picture which shows the algorithm: https://goo.gl/photos/E3QyKGgUjpKJFRRRA
    class Solution(object):
        def multiply(self, num1, num2):
            """
            :type num1: str
            :type num2: str
            :rtype: str
            """
            result = [0]*(len(num1) + len(num2))
            for i,x in enumerate(reversed(num1)):
                for j,y in enumerate(reversed(num2)):
                    a = int(x)*int(y) + result[i+j]
                    result[i+j] = int(a%10)
                    result[i+j+1] = result[i+j+1] + int(a/10)
            last = 0
            for i in range(len(result)-1, -1, -1):
                if result[i] != 0:
                    last = i
                    break
            answer = "".join(map(str, reversed(result[0:last+1])))
            return answer
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.