Subject to introduce

Force buckle 415: leetcode-cn.com/problems/ad…

Analysis of the

Instead of converting the input string directly to an integer, it is natural to break the string apart by each char, which is equivalent to iterating through each digit of the integer and then “multiplying by 10” to assemble it. This is the equivalent of “vertical addition” in arithmetic. We can’t use BigInteger’s built-in library to add large integers.

The code is as follows:

class Solution {
    public String addStrings(String num1, String num2){
       // Define a StringBuffer to hold the final result
       StringBuffer result = new StringBuffer();

       // Define the initial position for traversing two strings
       int i = num1.length() - 1;
       int j = num2.length() - 1;
       int carry = 0;    // Use a variable to hold the current carry

       // Start with the ones digit and continue as long as there is a number left uncounted. The other digits are filled with 0's
       while ( i >= 0 || j >= 0|| carry ! =0) {// Take the current corresponding digits of two numbers
           int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;     // character to convert ASCII codes to numbers
           int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;

           // Sum the current digit
           int sum = n1 + n2 + carry;

           // Store the ones bits of sum in the result, and the tens bits as carry
           result.append(sum % 10);
           carry = sum / 10;

           // Move the pointer over the next digit
           i --;
           j --;
       }
       returnresult.reverse().toString(); }}Copy the code

Complexity analysis

  • Time complexity: O(Max (len1,len2)), len1 = num1.length,len2 = num2.length. The number of vertical additions depends on the number of digits of the larger number.

  • Space complexity: O(n). The solution uses a StringBuffer, so the space complexity is O(n).