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

Notice

• The length of both num1 and num2 is < 5100.
• Both num1 and num2 contains only digits 0-9.
• Both num1 and num2 does not contain any leading zero.
• You must not use any built-in BigInteger library or convert the inputs to integer directly.

Have you met this question in a real interview?

Yes

Example

Given num1 ="123", num2 ="45"
return"168"

法一，先运算，再统一进位

class Solution:
    """
    @param num1: a non-negative integers
    @param num2: a non-negative integers
    @return: return sum of num1 and num2
    """
    def addStrings(self, num1, num2):
        # write your code here
        if not num1:
            return num2

        if not num2:
            return num1

        ans = [0 for i in xrange(max(len(num1), len(num2)) + 1)]
        i = len(num1) - 1
        j = len(num2) - 1
        k = len(ans) - 1
        while i >= 0 or j >= 0:
            cur = 0
            if i >= 0:
                ans[k] = ord(num1[i]) - ord('0')

            if j >= 0:
                ans[k] += ord(num2[j]) - ord('0')

            i -= 1
            j -= 1
            k -= 1

        k = len(ans) - 1
        while k > 0:
            ans[k - 1] += ans[k] / 10
            ans[k] %= 10
            k -= 1

        if len(ans) > 1 and ans[0] == 0:
            return "".join(str(i) for i in ans[1:])

        return "".join(str(i) for i in ans)

法二，一边运算一边进位

def addStrings(self, num1, num2):
        # write your code here
        if not num1:
            return num2
        if not num2:
            return num1

        ans = []
        i = len(num1) - 1
        j = len(num2) - 1
        carry = 0
        while i >= 0 or j >= 0:
            if i >= 0:
                carry += ord(num1[i]) - ord('0')
            if j >= 0:
                carry += ord(num2[j]) - ord('0')

            ans.append(carry % 10)
            carry /= 10
            i -= 1
            j -= 1

        if carry > 0:
            ans.append(carry)

        return "".join(str(i) for i in reversed(ans))