415. Add Strings

LeetCode 415. Add Strings

Description

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 = "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?

Tags

String

Solution

Loop to add characters from "the lowest bit" of both strings, and the loop condition is neither of two pointers is out of index, or the carry bit is non-zero. Obtained the sum of two bits and the carry, we update the result string by concatenating string(sum%10) and the old result string, meaning that we combining the single digit of the current summation, which is the result of a higher bit, with the lower bits that we have already calculated. Meanwhile, do not forget to update the carry. Finally return the result string.

Complexity

• Time complexity: $O(n)$, n for the length of the longer string

• Space complexity: $O(1)$

Code

func addStrings(num1 string, num2 string) string {
	var ans string
	var carry int
	for i, j := len(num1)-1, len(num2)-1; i >= 0 || j >= 0 || carry != 0; i, j = i-1, j-1 {
		sum := carry
		if i >= 0 {
			sum += int(num1[i] - '0')
		}
		if j >= 0 {
			sum += int(num2[j] - '0')
		}
		ans = strconv.Itoa(sum%10) + ans
		carry = sum / 10
	}
	return ans
}

Reference

1. 字符串相加