LeetCode 415 Add Strings

LeetCode 415 Add Strings

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

Note:

1. The length of both num1 and num2 is < 5100.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

题目大意：

给出两个字符串形式的非负数num1和num2，返回num1和num2之和。

解题思路：

对每一位进行加法，注意进位和长度不一，类似于merge sort里面merge的实现。最要注意的是进位carry的edge case：for循环后最后值要特别处理。

注意事项：

1. 三个循环后carry要特殊处理
2. Python中，题目要求不能用int函数，就只能用ord(num1[i]) - ord(‘0’)

Python代码：

def addStrings(self, num1: str, num2: str) -> str:
	num1, num2 = num1[::-1], num2[::-1]
	res = ''
	i, j, carry = 0, 0, 0
	while i < len(num1) or j < len(num2):
		tmp = carry
		if i < len(num1):
			tmp += ord(num1[i]) - ord('0')
			i += 1
		if j < len(num2):
			tmp += ord(num2[j]) - ord('0')
			j += 1
		carry = 1 if tmp >= 10 else 0
		res += str(tmp % 10)
	if carry == 1:
		res += str(carry)
	return res[::-1]

Java代码：

public String addStrings(String num1, String num2) {
	StringBuffer sb = new StringBuffer();
	int i=num1.length()-1,j=num2.length()-1;
	int carry=0;
	while(i>=0 && j>=0){
		int tmp = Integer.parseInt(num1.charAt(i)+"")+Integer.parseInt(num2.charAt(j)+"")+carry;
		if(tmp>=10)
			carry = 1;
		else carry = 0;
		sb.append(tmp%10);
		i--;
		j--;
	}
	while(i>=0){
		int tmp = Integer.parseInt(num1.charAt(i)+"")+carry;
		if(tmp>=10)
			carry = 1;
		else carry = 0;
		sb.append(tmp%10);
		i--;
	}
	while(j>=0){
		int tmp = Integer.parseInt(num2.charAt(j)+"")+carry;
		if(tmp>=10)
			carry = 1;
		else carry = 0;
		sb.append(tmp%10);
		j--;
	}
	if(carry>0)
		sb.append(carry);
	return sb.reverse().toString();	
}

算法分析：

时间复杂度为O(n)，n为字符串较长者长度。空间复杂度为O(1)。