A recursive solution to add two numbers represented as strings


  • -1
    H

    This code takes advantage of the fact that 182 * 72 = (100 + 80 + 2) * (70 + 2) in the core "multiply" function. From here, it's just adding numbers by the distributive law.

    The way I choose to add my integers represented by strings is by using recursion. The recursive function doesn't have any for loops in the base case, but sometimes calls the recursive function in the base case.

    class Solution(object):
        # @param {string} num1
        # @param {string} num2
        # @return {string}
        def multiply(self, num1, num2):
            decimals1 = num1.split()
            decimals1.reverse()
    
            decimals2 = num2.split()
            decimals2.reverse()
    
            total = ""
            for i, digit1 in enumerate(decimals1):
                for j, digit2 in enumerate(decimals2):
                    product = str(int(digit1) * int(digit2)) + ('0' * (i + j))
                    if product == "0": product = ""
                    total = self._add_strings(total, product, "")
    
            return "0" if total == "" else total
    
        def _add_strings(self, string1, string2, carry):
            """Adds two numbers represented as strings. Zero is
            represented by an empty string.
            """
            if len(string1) == 0:
    
                # Check if could recurse on other strings
                if len(string2) != 0 and len(carry) != 0:
                    return self._add_strings(string2, carry, "")
    
                # At least one of these needs to be the empty string
                return string2 if len(carry) == 0 else carry
    
            elif len(string2) == 0:
                if len(string1) != 0 and len(carry) != 0:
                    return self._add_strings(string1, carry, "")
                return string1 if len(carry) == 0 else carry
                
            # Recursive case
            temp = str(int(string1[-1]) + int(string2[-1]) + int(carry))
            return self._add_strings(string1[:-1], string2[:-1], temp[:-1]) + temp

Log in to reply
 

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