LeetCode Solutions Blog

Add Strings

Number: 415

Difficulty: Easy

Paid? No

Problem Description

Given two non-negative integers represented as strings, num1 and num2, return the sum of num1 and num2 as a string. The solution must simulate the addition process without using any built-in libraries to handle large integers or directly converting the strings to integers.

Key Insights

Process the input strings from the least significant digit (rightmost) to the most significant (leftmost).
Maintain a carry for sums exceeding a single digit.
Use a loop until all digits and any remaining carry have been processed.
Append the resulting digits (in reverse order) and then reverse the final string to obtain the correct result.
The approach simulates elementary addition as done by hand.

Space and Time Complexity

Time Complexity: O(max(n, m)) where n and m are the lengths of num1 and num2. Space Complexity: O(max(n, m)) for storing the result.

Solution

The solution uses two pointers that start at the end of each string to simulate digit-by-digit addition. At each step, digits from both strings are added along with the carry from the previous addition. The resulting digit is computed using modulo operation and the carry is updated using integer division. Each computed digit is then appended to a result list. Finally, the list is reversed and joined to form the final result string.

Code Solutions

# Define the function addStrings that takes two string inputs.
def addStrings(num1, num2):
    # Initialize pointers for num1 and num2 starting from the last character.
    i, j = len(num1) - 1, len(num2) - 1
    carry = 0  # Carry for addition result.
    result = []  # List to store the result digits.
    
    # Loop until both strings are processed or there's no remaining carry.
    while i >= 0 or j >= 0 or carry:
        # Get the digit from num1 if available, else use 0.
        d1 = int(num1[i]) if i >= 0 else 0
        # Get the digit from num2 if available, else use 0.
        d2 = int(num2[j]) if j >= 0 else 0
        
        # Compute the sum of the digits and the carry.
        total = d1 + d2 + carry
        
        # Append the current digit (total mod 10) to the result.
        result.append(str(total % 10))
        
        # Update the carry.
        carry = total // 10
        
        # Move to the next digits.
        i -= 1
        j -= 1
    
    # Reverse the result list and join to form the final string.
    return ''.join(result[::-1])

# Example usage:
print(addStrings("11", "123"))  # Expected output: "134"