415.Add Strings

Tags: [string_num_operation]

Link: https://leetcode.com/problems/add-strings/?tab=Description

Given two non-negative integersnum1andnum2represented as string, return the sum ofnum1andnum2.

Note:

1. The length of both num1and num2is < 5100.
2. Both num1and num2contains only digits 0-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.

Solution: string_num_operation

class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        if not num1:
            return num2
        if not num2:
            return num1

        rest = []
        carry = 0
        index_1 = len(num1) - 1
        index_2 = len(num2) - 1
        while index_1 >= 0 and index_2 >= 0:
            carry = self.push_result_digits([int(num1[index_1]), int(num2[index_2])], carry, rest)
            index_1 -= 1
            index_2 -= 1

        while index_1 >= 0:
            carry = self.push_result_digits([int(num1[index_1])], carry, rest)
            index_1 -= 1

        while index_2 >= 0:
            carry = self.push_result_digits([int(num2[index_2])], carry, rest)
            index_2 -= 1

        if carry:
            rest.append(str(carry))

        return ''.join(reversed(rest))

    @staticmethod
    def push_result_digits(digits, carry, rest):
        tmp_sum = sum(digits) + carry
        if tmp_sum < 10:
            rest.append(str(tmp_sum))
            return 0
        else:
            rest.append(str(tmp_sum % 10))
            return tmp_sum / 10

Note:

• Time complexity = O(max(len1, len2)), len1 is the length of the num1, and len2 is the length of the num2.
• We should put the reusable functionality in the functions, if it will not reduce the readability.
• In Python, '<delimiter>'.join(), only can accept the iterable object as the input.
• In Python, arr.reverse() returns None.
• In Python, reversed(arr) returns the reversed array.