0415. Add Strings

Easy | String + Math | 28 ms (97.36%), 14.2 MB (83.13%)

❓ Problem Statement

Source: LeetCode - Add Strings GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

Constraints:

• 1 <= num1.length, num2.length <= 10^4

• num1 and num2 consist of only digits.

• num1 and num2 don't have any leading zeros except for the zero itself.

Input: num1 = "11", num2 = "123"
Output: "134"

Input: num1 = "456", num2 = "77"
Output: "533"

Input: num1 = "0", num2 = "0"
Output: "0"

💡 Ideas

Sum each character reversely by index indicators starting from the end.

Since two strings might have different lengths, we need to take care of the condition when either one of strings meets the beginning first.

🤖 Python3

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        
        # ==================================================
        #  String + Math                                   =
        # ==================================================
        # time  : O(max(m,n))
        # space : O(1)
        
        ans, carry = '', 0
        
        p1, p2 = len(num1) - 1, len(num2) - 1
        while(p1 >= 0 or p2 >= 0 or carry > 0):
            val1 = ord(num1[p1]) - ord('0') if p1 >= 0 else 0
            val2 = ord(num2[p2]) - ord('0') if p2 >= 0 else 0
            val = val1 + val2 + carry
            carry = val // 10
            val = val % 10
            
            ans = str(val) + ans
            p1 -= 1
            p2 -= 1
            
        return ans

🤖 Java

class Solution {
    /**
     * @time  : O(max(m,n))
     * @space : O(1)
     */
    
    public String addStrings(String num1, String num2) {
        int p1 = num1.length() - 1, p2 = num2.length() - 1, carry = 0;
        
        StringBuilder ans = new StringBuilder();
        
        while(p1 >= 0 || p2 >= 0 || carry > 0) {
            int val1 = (p1 >= 0) ? num1.charAt(p1--) - '0' : 0;
            int val2 = (p2 >= 0) ? num2.charAt(p2--) - '0' : 0;
            int val = val1 + val2 + carry;
            carry = val / 10;
            val = val % 10;
            
            ans.append(val);
        }
        
        return ans.reverse().toString();
    }
}