Java solution, without StringBuilder and don't need to reverse (beat 97.64%)


  • 1
    R

    The idea is the same as "Plus one"

    public String addBinary(String a, String b) {
        if (a == null) return b;
        if (b == null) return a;
        int len1 = a.length();
        int len2 = b.length();
        //make sure a is longer or equal to b
        if (len2 > len1) {
            return addBinary(b, a);
        }
        int diff = len1 - len2;
        char[] result = new char[len1 + 1];
        result[0] = '0';
        int lastNotOne = 0;
        int curIndex = 1;
        
        for (; curIndex <= diff; curIndex++) {
            result[curIndex] = a.charAt(curIndex - 1);
            if (a.charAt(curIndex - 1)  == '0') {
                lastNotOne = curIndex;
            } 
        }
       
        while (curIndex <= len1) {
            int newDigit = (a.charAt(curIndex - 1) - '0' ) + (b.charAt(curIndex - diff - 1) - '0');
            if (newDigit == 2) {
                result[lastNotOne] = '1';
                for (int i = lastNotOne + 1; i <= curIndex; i++) {
                    result[i] = '0';
                }
                lastNotOne = curIndex;
            } else if (newDigit == 0) {
                result[curIndex] = '0';
                lastNotOne = curIndex;
            } else {
                result[curIndex] = '1';
            }
            curIndex++;
        }
        return result[0] == '0' ? new String(result, 1, len1) : new String(result);
    }

Log in to reply
 

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