Given two binary strings, return their sum (also a binary string).
For example,
a =
b =
Return
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;
}
}
沒有留言:
張貼留言