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.

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

Example 1:

• Input: num1 = “11”, num2 = “123”
• Output: “134”

Example 2:

• Input: num1 = “456”, num2 = “77”
• Output: “533”

Example 3:

• Input: num1 = “0”, num2 = “0”
• Output: “0”

Constraints:

• 1 <= num1.length, num2.length <= 10⁴
• num1 and num2 consist of only digits.
• num1 and num2 don’t have any leading zeros except for the zero itself.

Submitted Code

class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        if len(num1) != len(num2):
            length = max(len(num1), len(num2))
            num1 = num1.zfill(length)
            num2 = num2.zfill(length)
        else:
            length = len(num1)

        carry = 0
        result = []
        for i in range((length - 1), -1, -1):
            digit1 = ord(num1[i]) - ord("0")  # ord("0") == 48
            digit2 = ord(num2[i]) - ord("0")

            sum = digit1 + digit2 + carry
            if sum > 9:
                carry = 1
                sum -= 10
            else:
                carry = 0

            result.append(chr(sum + ord("0")))
        
        return "1" + "".join(result[::-1]) if carry == 1 else "".join(result[::-1])    

Runtime: 2 ms | Beats 73.82%
Memory: 12.80 MB | Beats 17.23%

zfill()을 이용하여 길이가 더 짧은 쪽의 앞에 0을 채워넣어 두 문자열의 길이를 맞췄다. 그리고 문자열을 정수로 바로 변환하는 것이 금지되었기 때문에 아스키코드로 바꾼 후 ord("0")을 빼는 방법을 사용하여 정수값을 얻었다. 결과값은 문자열보다 리스트로 설정하는 것이 훨씬 빨랐다.

Other Solutions

1st

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        idx1 = len(num1) - 1
        idx2 = len(num2) - 1
        small_ascii = ord('0')  # ASCII of '0' is 48
        base = 10
        carry = 0
        result = []

        while idx1 >= 0 or idx2 >= 0:
            n1 = ord(num1[idx1]) - small_ascii if idx1 >= 0 else 0
            n2 = ord(num2[idx2]) - small_ascii if idx2 >= 0 else 0
            total = n1 + n2 + carry
            carry = total // base
            result.append(str(total % base))
            idx1 -= 1
            idx2 -= 1

        if carry:
            result.append(str(carry))

        return ''.join(reversed(result))

time complexity: 𝑂(max(𝑛,𝑚))
space complexity: 𝑂(max(𝑛,𝑚))

zfill() 함수 없이 인덱스로만 추적하는 것이 더 깔끔한 것 같다.

2nd

class Solution:
    def addStrings(self, num1, num2):
        numDict = {'0' : 0, '1' : 1, '2' : 2, '3' : 3, '4' : 4, '5' : 5,'6' : 6, '7' : 7, '8' : 8, '9' : 9}
        ans1=0
        ans2=0
        for d in num1:
            ans1=ans1*10+numDict[d]
        for d in num2:
            ans2=ans2*10+numDict[d]
        return str(ans1+ans2)

딕셔너리를 이용해서 str → int 변환 과정을 함수없이 해결한 답안이다.

num1 = “11”
num2 = “123”

ans1   d
0      1  → (0 * 10) + 1 = 1
1      1  → (1 * 10) + 1 = 11
11

ans2   d
0      1  → (0 * 10) + 1 = 1
1      2  → (1 * 10) + 2 = 12
12     3  → (12* 10) + 3 = 123
123

str(11 + 123) = str(134)

return “134”