2014年4月18日 星期五

[LeetCode] Add Binary

Problem:
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
Solution:O(n)
public class Solution {
    public String addBinary(String a, String b) {
        if(a.length() == 0)
            return b;
        if(b.length() == 0)
            return a;
            
        if(a.length() > b.length())
            return addBinary(b,a);
            
        String buf = "";
        int carry = 0;
        for(int i=0; i<b.length();i++){
            int left = 0;
            int right = b.charAt(b.length()-i-1)-'0';
            if(i<a.length())
             left = a.charAt(a.length()-i-1)-'0'; 
         int sum =  left+ right + carry;
            carry = sum/2;
            buf = "" + (sum%2) + buf;
        }
        if(carry == 1)
            buf = "1"+buf;
        return buf;
    }
}

沒有留言:

張貼留言