Python divide and conque solution does not pass, idea for optimization?


  • 0
    G
    class Solution:
    # @param {string} num1
    # @param {string} num2
    # @return {string}
    def multiply(self, num1, num2):
        # AB * CD
        if not num1 or not num2:
            return '0'
        if len(num1) == len(num2) == 1:
            return str(int(num1) * int(num2))
    
        p1 = len(num1) // 2
        p2 = len(num2) // 2
        parts = [
            self.multiply(num1[:p1], num2[:p2]) + '0' * (len(num1)-p1 + len(num2)-p2),
            self.multiply(num1[p1:], num2[:p2]) + '0' * (len(num2)-p2),
            self.multiply(num1[:p1], num2[p2:]) + '0' * (len(num1)-p1),
            self.multiply(num1[p1:], num2[p2:])
        ]
        stack = []
        ans = []
        parts.append('')
        while True:
            for i, p in enumerate(parts):
                if p:
                    stack.append(int(p[-1]))
                    parts[i] = p[:-1]
            if not stack:
                break
            result = str(sum(stack))
            stack = []
            ans.append(result[-1])
            if (len(result) > 1):
                parts[4] = result[:-1]
        return (''.join(reversed(ans))).lstrip('0')

Log in to reply
 

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