#67. Add Binary

題目描述

給你兩個表示二進位的字串a和b，回傳相加後的字串。

限制條件

1. 1 <= a.length, b.length <= 104
2. a和b只會由0和1組成。
3. 每個字串不包含零值開頭，除了0之外。

解題思路

最簡單的方式就是字串相加，把a和b相加後形成新的字串。

String & Math

public class Solution {
	public string AddBinary(string a, string b) {
        bool carry = false;
        var ans = new StringBuilder();
        int a_len = a.Length-1;
        int b_len = b.Length-1;
        while(a_len>=0 || b_len>=0){
            ans.Insert(0,"0");            
            if(carry) {
                ans[0] = '1';
                carry = false;
            }
            if(a_len>=0){
                if(a[a_len]=='1'){
                    if(ans[0]=='1') {
                        ans[0] = '0';
                        carry = true;
                    }else{
                         ans[0] = '1';
                    }
                }
                a_len--;
            }
            if(b_len>=0){
                if(b[b_len]=='1'){
                    if(ans[0]=='1') {
                        ans[0] = '0';
                        carry = true;
                    }else{
                         ans[0] = '1';
                    }
                }
                b_len--;
            }                        
        }
        if(carry) ans.Insert(0,"1");
        return ans.ToString();
    }
}

複雜度分析：

• 時間複雜度：取決於a和b其中最長的那一段，因此時間複雜度為O(Max(m,n))。
• 空間複雜度：使用了StringBuilder來創造新的字串，而新字串的長度最長會等於a和b之間最長的的字串再加上是否有進位，因此空間複雜度為O(Max(m,n))。

學習重點

• 二進位計算
• 字串處理