415.Add_Strings(Easy).md

415. Add Strings (Easy)

Date and Time: Dec 17, 2024, 11:40 (EST)

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

Question:

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

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

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"

Edge Case:

Input: num1 = "1", num2 = "9"

Output: "10"

Constraints:

• 1 <= num1.length, num2.length <= 10^4

• num1 and num2 consist of only digits.

• num1 and num2 don't have any leading zeros except for the zero itself.

Walk-through:

This question is very similar to 2. Add Two Numbers.

We use two ptrs i, j to get the digits from num1, num2 backward. If one of the index is out of bound, we set it to be 0. And we also add carry together and append the result into res[]. We update carry = two chars sum + carry // 10 so carry will be either 0 or 1.

After that, we check if carry, so we won't miss to add carry into res[].

Finally, reverse res[] and convert each int() to str() and join them.

Python Solution:

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        # Use i, j to access num1, num2 chars backward, if i or j is out of bound, set to 0
        # Append to res[] by taking sum of int(num1[i]) + int(num2[j]) + carry, then update carry
        # Check if remaining carry exists, append it
        # Reverse the res[], convert and join them

        # TC: O(max(n, m)), n=len(num1), m=len(num2), SC: O(max(n, m))
        i, j = len(num1)-1, len(num2)-1
        res, carry = [], 0
        while i >= 0 or j >= 0:
            c1 = num1[i] if i >= 0 else 0
            c2 = num2[j] if j >= 0 else 0
            res.append((int(c1) + int(c2) + carry) % 10)
            carry = (int(c1) + int(c2) + carry) // 10
            i, j = i - 1, j - 1
        # Check carry for extra char
        if carry:
            res.append(carry)
        return "".join(str(c) for c in res[::-1])

Time Complexity: $O(max(n, m))$
Space Complexity: $O(max(n, m))$