Add Strings

https://leetcode.com/problems/add-strings/description/

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2

Thoughts

常见实现加法器套路. 从后往前一位一位的加, 配合carry. 最后carry可能不为0, 那时还要+1.

Code

class Solution {

    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int i = num1.length() - 1, j = num2.length() - 1;
        int carry = 0;
        while (i >= 0 && j >= 0) {
            char a = num1.charAt(i);
            char b = num2.charAt(j);
            int sum = (a - '0') + (b - '0') + carry;
            if (sum >= 10) {
                carry = 1;
            } else {
                carry = 0;
            }
            sb.insert(0, sum % 10);
            i--;
            j--;
        }

        while (i >= 0) {
            char a = num1.charAt(i);
            int sum = (a - '0') + carry;
            if (sum >= 10) {
                carry = 1;
            } else {
                carry = 0;
            }
            sb.insert(0, sum % 10);
            i--;
        }

        while (j >= 0) {
            char b = num2.charAt(j);
            int sum = (b - '0') + carry;
            if (sum >= 10) {
                carry = 1;
            } else {
                carry = 0;
            }
            sb.insert(0, sum % 10);
            j--;
        }

        if (carry != 0) {
            sb.insert(0, 1);
        }

        return sb.toString();
    }
}

Analysis

时空复杂度都是O(N).

Ver.2

class Solution {

    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        for (int i = num1.length() - 1, j = num2.length() - 1, carry = 0; i >= 0 || j >= 0 || carry != 0; i--, j--) {
            int a = i >= 0 ? num1.charAt(i) - '0' : 0;
            int b = j >= 0 ? num2.charAt(j) - '0' : 0;
            int sum = a + b + carry;
            carry = sum >= 10 ? 1 : 0;
            sb.insert(0, sum % 10);   
        }

        return sb.toString();
    }
}