Share my simple java solution


  • 1
    I
    public String addBinary(String a, String b) {
        int carry = 0;
        int l1 = a.length() - 1;
        int l2 = b.length() - 1;
        StringBuilder sb = new StringBuilder();
        while (l1 >= 0 || l2 >= 0 || carry != 0) {
            int tmp = (l1 >= 0 ?  Integer.parseInt(a.charAt(l1--)+"") : 0) + (l2 >= 0 ?  Integer.parseInt(b.charAt(l2--)+"") : 0) + carry;
            carry = tmp >= 2 ? 1 : 0;
            sb.insert(0, tmp % 2 == 0 ? '0' : '1');
        }
        if (sb.charAt(0) == '0') {
            return "0";
        }
        return sb.toString();
    }

  • 0
    S

    StringBuilder is handy, but StringBuilder.insert(0, Object) is O(N) time complexity which leads to a O(N^2) overall time complexity.

    I may suggest to append first then reverse the whole buffer after the main loop. It will guarantee O(N) time complexity.


  • 0
    I

    Yeah, you are right, thank you for your suggestion!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.