LeetCode 415. Add Strings

Description

https://leetcode.com/problems/add-strings/

Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.

Example 1:

Input: num1 = "11", num2 = "123"
Output: "134"

Example 2:

Input: num1 = "456", num2 = "77"
Output: "533"

Example 3:

Input: num1 = "0", num2 = "0"
Output: "0"

Constraints:

  • 1 <= num1.length, num2.length <= 104
  • num1 and num2 consist of only digits.
  • num1 and num2 don’t have any leading zeros except for the zero itself.

Follow up: Could you solve it without using any built-in BigInteger library or converting the inputs to integer directly?

Explanation

Sum the two num strings by digits.

Python Solution

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        num1s = []
        for c in num1:
            num1s.insert(0, int(c))
        
        num2s = []
        for c in num2:
            num2s.insert(0, int(c))

        i = 0
        j = 0
        carry = 0

        results = []
        while i < len(num1s) and j < len(num2s):
            digit = (num1s[i] + num2s[j] + carry) % 10
            carry = (num1s[i] + num2s[j] + carry) // 10
            results.insert(0, str(digit))
            i += 1
            j += 1

        while i < len(num1s):
            digit = (num1s[i] + carry) % 10
            carry = (num1s[i] + carry) // 10
            results.insert(0, str(digit))
            i += 1

        while j < len(num2s):
            digit = (num2s[j] + carry) % 10
            carry = (num2s[j] + carry) // 10
            results.insert(0, str(digit))
            j += 1

        if carry > 0:
            results.insert(0, str(carry))
                    
        return "".join(results)
            
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.