# Add Binary ### Source - leetcode: [Add Binary | LeetCode OJ](https://leetcode.com/problems/add-binary/) - lintcode: [(408) Add Binary](http://www.lintcode.com/en/problem/add-binary/) ~~~ Given two binary strings, return their sum (also a binary string). For example, a = "11" b = "1" Return "100". ~~~ ### 題解 用字符串模擬二進制的加法，加法操作一般使用自后往前遍歷的方法，不同位大小需要補零。 ### Java ~~~ public class Solution { /** * @param a a number * @param b a number * @return the result */ public String addBinary(String a, String b) { if (a == null || a.length() == 0) return b; if (b == null || b.length() == 0) return a; StringBuilder sb = new StringBuilder(); int aLen = a.length(), bLen = b.length(); int carry = 0; for (int ia = aLen - 1, ib = bLen - 1; ia >= 0 || ib >= 0; ia--, ib--) { // replace with 0 if processed int aNum = (ia < 0) ? 0 : a.charAt(ia) - '0'; int bNum = (ib < 0) ? 0 : b.charAt(ib) - '0'; int num = (aNum + bNum + carry) % 2; carry = (aNum + bNum + carry) / 2; sb.append(num); } if (carry == 1) sb.append(1); // important! sb.reverse(); String result = sb.toString(); return result; } } ~~~ ### 源碼分析 用到的技巧主要有兩點，一是兩個數位數大小不一時用0補上，二是最后需要判斷最高位的進位是否為1。最后需要反轉字符串，因為我們是從低位往高位迭代的。雖然可以使用 insert 避免最后的 reverse 操作，但如此一來時間復雜度就從 O(n)O(n)O(n) 變為 O(n2)O(n^2)O(n2) 了。 ### 復雜度分析 遍歷兩個字符串，時間復雜度 O(n)O(n)O(n). reverse 操作時間復雜度 O(n)O(n)O(n), 故總的時間復雜度 O(n)O(n)O(n). 使用了 StringBuilder 作為臨時存儲對象，空間復雜度 O(n)O(n)O(n).