1, Title Requirements

• Given two non negative integers num1 and num2 in string form, calculate their sum and return them in string form as well.
• You cannot use any built-in library for handling large integers (such as BigInteger), nor can you directly convert the input string to integer form.
• 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"

• Tips:
• • 1 <= num1.length, num2.length <= 104；
• • Both num1 and num2 contain only the numbers 0-9;
• • Neither num1 nor num2 contains any leading zeros.

2, Solving algorithm

① Simulation

• This question only needs to simulate the process of "vertical addition" for two large integers. Vertical addition is the method of adding two integers commonly used in daily study and life. Recall the operation of adding two integers on paper. Is it right to align the same digits and add them bit by bit from low to high as shown in the following figure? If the sum of the current bit exceeds 10, move one bit to the high position? So just write this process in code.

• The specific implementation is not complicated. Define two pointers i and j to point to the end of num1 and num2 respectively, that is, the lowest bit. At the same time, define a variable add to maintain whether there is carry at present, and then add bit by bit from the end to the beginning. You may wonder how to deal with the difference in the number of digits of two numbers. Here, we uniformly return 0 when the current subscript of the pointer is negative, which is equivalent to the zero filling operation for the number with short digits. In this way, we can eliminate the treatment of different numbers of two numbers.
• C + + example:

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        string ans = "";
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1[i] - '0' : 0;
            int y = j >= 0 ? num2[j] - '0' : 0;
            int result = x + y + add;
            ans.push_back('0' + result % 10);
            add = result / 10;
            i -= 1;
            j -= 1;
        }
        // After the calculation, the answer needs to be turned over
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

• Java example:

class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        // After the calculation, the answer needs to be turned over
        ans.reverse();
        return ans.toString();
    }
}

② Double pointer

• Set n1 and n2 pointers to the tail of num1 and num2 respectively to simulate manual addition;
• • Calculate carry: calculate carry = tmp // 10, which indicates whether the current bit is added to generate carry;
• • Add current bit: calculate tmp = n1 + n2 + carry, and add current bit TMP% 10 to res header;
• • Index overflow processing: when the pointer n1 or n2 passes through the head of the number, assign a value of 0 to n1 and n2, which is equivalent to filling 0 in front of the shorter number in num1 and num2 for subsequent calculation.
• • After traversing num1 and num2, jump out of the loop, decide whether to add carry 1 to the header according to the carry value, and finally return to res.
• Initial state:

• n1 and n2 pointers point to the tail of num1 and num2 respectively:

• n1 and n2 pointers continue to point to the ten bits of num1 and num2 respectively:

• And so on until the highest position:

• The final results are as follows:

• Java example:

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder res = new StringBuilder("");
        int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
        while(i >= 0 || j >= 0){
            int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
            int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
            int tmp = n1 + n2 + carry;
            carry = tmp / 10;
            res.append(tmp % 10);
            i--; j--;
        }
        if(carry == 1) res.append(1);
        return res.reverse().toString();
    }
}

• Python example:

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        res = ""
        i, j, carry = len(num1) - 1, len(num2) - 1, 0
        while i >= 0 or j >= 0:
            n1 = int(num1[i]) if i >= 0 else 0
            n2 = int(num2[j]) if j >= 0 else 0
            tmp = n1 + n2 + carry
            carry = tmp // 10
            res = str(tmp % 10) + res
            i, j = i - 1, j - 1
        return "1" + res if carry else res