LeetCode 415: Add Strings Solution in Python – A Step-by-Step Guide

What Is LeetCode 415: Add Strings?

In LeetCode 415: Add Strings, you’re given two strings num1 and num2 (e.g., "123" and "456"), each representing a non-negative integer with only digits 0-9 and no leading zeros (except for "0" itself). Your task is to return their sum as a string (e.g., "579") without converting them to integers directly—think of it as pure digit-by-digit addition. For example, "123" + "456" = "579," and "11" + "123" = "134," handling carries just like you’d do by hand.

Problem Statement

• Input: Two strings num1 and num2 (non-negative integers).
• Output: A string—the sum of num1 and num2.
• Rules:
• No direct conversion to integers (e.g., no int(num1)).
• No leading zeros in inputs (except "0").
• Handle carries like manual addition.

Constraints

• 1 <= num1.length, num2.length <= 10⁴.
• num1 and num2 contain only digits 0-9.
• No leading zeros in num1 or num2 unless the number is "0".

Examples

• Input: num1 = "123", num2 = "456"
• Output: "579".
• Input: num1 = "11", num2 = "123"
• Output: "134".
• Input: num1 = "456", num2 = "77"
• Output: "533".

Understanding the Problem: Adding Digits as Strings

To solve LeetCode 415: Add Strings in Python, we need to add two numbers represented as strings, digit by digit, without turning them into integers. A naive idea might be to convert them anyway—but that’s against the rules and risky with big numbers! Instead, we’ll use:

• Best Solution (Two-Pointer Iteration): O(max(n,m)) time, O(1) space (excluding output)—adds from right to left.
• Alternative Solution (Stack-Based): O(max(n,m)) time, O(n+m) space—builds with stacks.

Let’s dive into the two-pointer solution with a clear, step-by-step explanation.

Best Solution: Two-Pointer Iteration

Why This Is the Best Solution

The two-pointer iteration method is the top pick because it’s fast—O(max(n,m)) time, O(1) space (not counting the output)—and mimics how you’d add numbers by hand. It uses two pointers to walk backward through both strings, summing digits and tracking carries, building the result from right to left in one pass. It’s like lining up your numbers on paper and adding column by column!

How It Works

Think of the strings as two stacks of digits you’re adding:

• Step 1: Set Up Pointers:
• Start at the right end of both strings (e.g., "3" in "123", "6" in "456").
• Track a carry (starts at 0).
• Step 2: Add Digits:
• For each position:
• Get digits (0 if out of bounds).
• Sum = digit1 + digit2 + carry.
• New digit = sum % 10, carry = sum // 10.
• Add new digit to result (prepend).
• Step 3: Handle Leftover Carry:
• If carry remains, prepend it (e.g., "1" for "99" + "1").
• Step 4: Why This Works:
• Right-to-left mimics manual addition.
• No extra space beyond the result string.
• It’s like doing your math homework without a calculator!

Step-by-Step Example

Example: num1 = "123", num2 = "456"

• Start: i = 2, j = 2, carry = 0, result = "".
• i=2, j=2: "3" + "6" = 9, carry = 0, result = "9".
• i=1, j=1: "2" + "5" = 7, carry = 0, result = "79".
• i=0, j=0: "1" + "4" = 5, carry = 0, result = "579".
• End: No carry, result = "579".
• Result: "579".

Example: num1 = "11", num2 = "123"

• i=1, j=2: "1" + "3" = 4, carry = 0, result = "4".
• i=0, j=1: "1" + "2" = 3, carry = 0, result = "34".
• i=-1, j=0: "0" + "1" = 1, carry = 0, result = "134".
• Result: "134".

Example: num1 = "99", num2 = "1"

• i=1, j=0: "9" + "1" = 10, carry = 1, result = "0".
• i=0, j=-1: "9" + "0" + 1 = 10, carry = 1, result = "00".
• i=-1, j=-1: Carry = 1, result = "100".
• Result: "100".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        # Step 1: Set pointers and carry
        i = len(num1) - 1  # Right end of num1
        j = len(num2) - 1  # Right end of num2
        carry = 0
        result = ""

        # Step 2: Add digits from right to left
        while i >= 0 or j >= 0 or carry:
            # Get digits, use 0 if out of bounds
            digit1 = int(num1[i]) if i >= 0 else 0
            digit2 = int(num2[j]) if j >= 0 else 0

            # Calculate sum and new carry
            total = digit1 + digit2 + carry
            digit = total % 10
            carry = total // 10

            # Prepend digit to result
            result = str(digit) + result

            # Move pointers
            i -= 1
            j -= 1

        return result

• Line 4-7: Initialize:
• i, j: Start at right ends (e.g., 2 for "123").
• carry: Starts at 0.
• result: Empty string to build sum.
• Line 10-21: Loop while digits or carry remain:
• Line 11-12: Get digits, 0 if past end (e.g., i=-1 → 0).
• Line 15-17: Sum digits + carry, split into digit (mod 10) and carry (div 10).
• Line 19: Prepend digit (e.g., "9" + "" = "9").
• Line 21-22: Move pointers left.
• Line 24: Return final string.
• Time Complexity: O(max(n,m))—process longer string’s length.
• Space Complexity: O(1)—excluding output, just a few variables.

This is like adding numbers on paper, step-by-step!

Alternative Solution: Stack-Based Approach

Why an Alternative Approach?

The stack-based method uses two stacks to pop digits from the right, summing them and building the result with another stack. It’s O(max(n,m)) time and O(n+m) space—more visual but uses extra memory. It’s like stacking digits in trays and pouring them into a sum pile!

How It Works

Picture it as stacking and summing:

• Step 1: Push digits into stacks for num1 and num2.
• Step 2: Pop and add digits, track carry, push to result stack.
• Step 3: Pop result stack to build string.

Step-by-Step Example

Example: num1 = "123", num2 = "456"

• Stacks: num1_stack = [1,2,3], num2_stack = [4,5,6].
• Sum:
• 3 + 6 = 9, carry = 0, result_stack = [9].
• 2 + 5 = 7, carry = 0, result_stack = [7,9].
• 1 + 4 = 5, carry = 0, result_stack = [5,7,9].
• Build: "579".
• Result: "579".

Code for Stack-Based Approach

Copy codeclass Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        # Step 1: Convert to stacks
        stack1 = list(num1)
        stack2 = list(num2)
        carry = 0
        result_stack = []

        # Step 2: Add digits
        while stack1 or stack2 or carry:
            digit1 = int(stack1.pop()) if stack1 else 0
            digit2 = int(stack2.pop()) if stack2 else 0
            total = digit1 + digit2 + carry
            digit = total % 10
            carry = total // 10
            result_stack.append(str(digit))

        # Step 3: Build result
        return "".join(result_stack[::-1])

• Time Complexity: O(max(n,m))—process all digits.
• Space Complexity: O(n+m)—stacks for input and result.

It’s a stack-pouring sum builder!

Comparing the Two Solutions

• Two-Pointer Iteration (Best):
• Pros: O(max(n,m)), O(1), fast and lean.
• Cons: Less visual.
• Stack-Based (Alternative):
• Pros: O(max(n,m)), O(n+m), intuitive stacking.
• Cons: More space.

Two-pointer wins for efficiency.

Additional Examples and Edge Cases

• "0", "0": "0".
• "999", "1": "1000".
• "1", "12345": "12346".

Two-pointer handles all.

Complexity Breakdown

• Two-Pointer: Time O(max(n,m)), Space O(1).
• Stack-Based: Time O(max(n,m)), Space O(n+m).

Two-pointer’s the champ.

Key Takeaways

• Two-Pointer: Add in place!
• Stack-Based: Pile it up!
• Strings: Digits dance.
• Python Tip: Strings rock—see [Python Basics](/python/basics).

Final Thoughts: Sum Those Strings

LeetCode 415: Add Strings in Python is a digit-adding adventure. Two-pointer iteration sums it smoothly, while stacks pile it creatively. Want more string fun? Try LeetCode 67: Add Binary or LeetCode 43: Multiply Strings. Ready to add? Head to Solve LeetCode 415 on LeetCode and string that sum today!