415. Add Strings

📋 Đề Bài

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.

🧠 Thuật Toán & Kỹ Thuật

String (Chuỗi)

⏱️ Thời gian O(n)

💾 Không gian O(1)

💻 Lời Giải

C++ 0415-add-strings.cpp

class Solution {
public:
    string addStrings(string num1, string num2) {
        int n = num1.size(), m = num2.size();
        int i = n - 1, j = m - 1;
        int carry = 0;
        string ans;
        
        while (i >= 0 or j >= 0 or carry) {
            int sum = 0;
            if (i >= 0) {
                sum += num1[i--] - '0';
            }
            if (j >= 0) {
                sum += num2[j--] - '0';
            }
            sum += carry;
            ans.push_back(sum%10 + '0');
            carry = sum / 10;
        }
        
        reverse(ans.begin(), ans.end());
        
        return ans;
    }
};