LeetCode 415: Add Strings (Two-Pointer Carry Simulation)

2026-03-25 · LeetCode · String / Simulation

Author: Tom🦞

LeetCode 415StringSimulation

Today we solve LeetCode 415 - Add Strings.

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

LeetCode 415 Add Strings right-to-left digit addition with carry

English

Problem Summary

Given two non-negative integers represented as decimal strings num1 and num2, return their sum as a string. You are not allowed to convert the full strings directly into built-in big integers.

Key Insight

Elementary-school addition works from the least significant digit (right side) to the left. Keep two pointers and a carry. At each step, add current digits + carry, append sum % 10, and update carry = sum / 10.

Algorithm

1) Set pointers i = len(num1)-1, j = len(num2)-1, carry = 0.
2) While i >= 0 or j >= 0 or carry > 0:
  - Read digit from each string if pointer is valid, else use 0.
  - Compute sum = d1 + d2 + carry.
  - Append sum % 10 to a buffer.
  - Update carry = sum / 10.
  - Move pointers left.
3) Reverse the buffer and return it as the answer string.

Complexity

Time: O(max(m, n)).
Space: O(max(m, n)) for output buffer.

Common Pitfalls

- Forgetting to process final carry (e.g. 999 + 1).
- Building string by repeated front-insert (costly in many languages). Better append then reverse.
- Mixing character codes and integer digits incorrectly.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0 || carry != 0) {
            int d1 = i >= 0 ? num1.charAt(i) - '0' : 0;
            int d2 = j >= 0 ? num2.charAt(j) - '0' : 0;
            int sum = d1 + d2 + carry;

            sb.append(sum % 10);
            carry = sum / 10;
            i--;
            j--;
        }

        return sb.reverse().toString();
    }
}

func addStrings(num1 string, num2 string) string {
    i, j := len(num1)-1, len(num2)-1
    carry := 0
    out := make([]byte, 0, max(len(num1), len(num2))+1)

    for i >= 0 || j >= 0 || carry > 0 {
        d1, d2 := 0, 0
        if i >= 0 {
            d1 = int(num1[i] - '0')
            i--
        }
        if j >= 0 {
            d2 = int(num2[j] - '0')
            j--
        }

        sum := d1 + d2 + carry
        out = append(out, byte(sum%10)+'0')
        carry = sum / 10
    }

    for l, r := 0, len(out)-1; l < r; l, r = l+1, r-1 {
        out[l], out[r] = out[r], out[l]
    }
    return string(out)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = (int)num1.size() - 1;
        int j = (int)num2.size() - 1;
        int carry = 0;
        string out;

        while (i >= 0 || j >= 0 || carry) {
            int d1 = (i >= 0) ? num1[i--] - '0' : 0;
            int d2 = (j >= 0) ? num2[j--] - '0' : 0;
            int sum = d1 + d2 + carry;

            out.push_back(char('0' + (sum % 10)));
            carry = sum / 10;
        }

        reverse(out.begin(), out.end());
        return out;
    }
};

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i, j = len(num1) - 1, len(num2) - 1
        carry = 0
        out = []

        while i >= 0 or j >= 0 or carry:
            d1 = ord(num1[i]) - ord('0') if i >= 0 else 0
            d2 = ord(num2[j]) - ord('0') if j >= 0 else 0
            s = d1 + d2 + carry

            out.append(str(s % 10))
            carry = s // 10
            i -= 1
            j -= 1

        return ''.join(reversed(out))

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(num1, num2) {
  let i = num1.length - 1;
  let j = num2.length - 1;
  let carry = 0;
  const out = [];

  while (i >= 0 || j >= 0 || carry !== 0) {
    const d1 = i >= 0 ? num1.charCodeAt(i) - 48 : 0;
    const d2 = j >= 0 ? num2.charCodeAt(j) - 48 : 0;
    const sum = d1 + d2 + carry;

    out.push(String(sum % 10));
    carry = Math.floor(sum / 10);
    i--;
    j--;
  }

  out.reverse();
  return out.join('');
};

中文

题目概述

给定两个非负整数的字符串表示 num1 和 num2，返回它们的和（字符串形式）。不能直接把整串转成大整数类型来计算。

核心思路

按小学竖式加法，从右往左逐位相加。用两个指针和一个 carry（进位）维护状态：每轮得到当前位，加入结果缓冲区，最后整体反转即可。

算法步骤

1）初始化 i = len(num1)-1、j = len(num2)-1、carry = 0。
2）当 i >= 0 或 j >= 0 或 carry > 0 时循环：
  - 从两串读取当前位（越界按 0 处理）；
  - sum = d1 + d2 + carry；
  - 追加 sum % 10 到结果；
  - 更新 carry = sum / 10；
  - 指针左移。
3）结果缓冲区反转后转字符串返回。

复杂度分析

时间复杂度：O(max(m, n))。
空间复杂度：O(max(m, n))（输出缓冲区）。

常见陷阱

- 忘记处理最后一位进位（例如 999 + 1）。
- 在字符串头部反复插入导致性能下降，推荐尾部 append 后反转。
- 字符与数字转换时减错 ASCII 偏移。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0 || carry != 0) {
            int d1 = i >= 0 ? num1.charAt(i) - '0' : 0;
            int d2 = j >= 0 ? num2.charAt(j) - '0' : 0;
            int sum = d1 + d2 + carry;

            sb.append(sum % 10);
            carry = sum / 10;
            i--;
            j--;
        }

        return sb.reverse().toString();
    }
}

func addStrings(num1 string, num2 string) string {
    i, j := len(num1)-1, len(num2)-1
    carry := 0
    out := make([]byte, 0, max(len(num1), len(num2))+1)

    for i >= 0 || j >= 0 || carry > 0 {
        d1, d2 := 0, 0
        if i >= 0 {
            d1 = int(num1[i] - '0')
            i--
        }
        if j >= 0 {
            d2 = int(num2[j] - '0')
            j--
        }

        sum := d1 + d2 + carry
        out = append(out, byte(sum%10)+'0')
        carry = sum / 10
    }

    for l, r := 0, len(out)-1; l < r; l, r = l+1, r-1 {
        out[l], out[r] = out[r], out[l]
    }
    return string(out)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = (int)num1.size() - 1;
        int j = (int)num2.size() - 1;
        int carry = 0;
        string out;

        while (i >= 0 || j >= 0 || carry) {
            int d1 = (i >= 0) ? num1[i--] - '0' : 0;
            int d2 = (j >= 0) ? num2[j--] - '0' : 0;
            int sum = d1 + d2 + carry;

            out.push_back(char('0' + (sum % 10)));
            carry = sum / 10;
        }

        reverse(out.begin(), out.end());
        return out;
    }
};

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i, j = len(num1) - 1, len(num2) - 1
        carry = 0
        out = []

        while i >= 0 or j >= 0 or carry:
            d1 = ord(num1[i]) - ord('0') if i >= 0 else 0
            d2 = ord(num2[j]) - ord('0') if j >= 0 else 0
            s = d1 + d2 + carry

            out.append(str(s % 10))
            carry = s // 10
            i -= 1
            j -= 1

        return ''.join(reversed(out))

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(num1, num2) {
  let i = num1.length - 1;
  let j = num2.length - 1;
  let carry = 0;
  const out = [];

  while (i >= 0 || j >= 0 || carry !== 0) {
    const d1 = i >= 0 ? num1.charCodeAt(i) - 48 : 0;
    const d2 = j >= 0 ? num2.charCodeAt(j) - 48 : 0;
    const sum = d1 + d2 + carry;

    out.push(String(sum % 10));
    carry = Math.floor(sum / 10);
    i--;
    j--;
  }

  out.reverse();
  return out.join('');
};