---
# System prepended metadata

title: 'Add Binary <img src="https://img.shields.io/badge/-easy-brightgreen">'
tags: [data_structure_python]

---

---
tags: data_structure_python
---

# Add Binary <img src="https://img.shields.io/badge/-easy-brightgreen">

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters ```1``` or ```0```.

<ins>**Example 1:**</ins>

>Input: a = "11", b = "1"
>Output: "100"

<ins>**Example 2:**</ins>

>Input: a = "1010", b = "1011"
>Output: "10101"

# Solution

```python=
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        dic = {'1': 1, '0': 0}
        res, carry = "", 0
        n, m = len(a) , len(b)
        
        if n < m:
            a = "0" * (m-n) + a
        else:
            b = "0" * (n-m) + b            
        
        n = len(a)
        i=0
        while i < n:
            
            if dic[a[n-1-i]] == 1 and dic[b[n-1-i]] == 1:
                if carry:
                    res = "1" + res
                else:
                    res = "0" + res
                carry = 1
            else:
                tmp = (dic[a[n-1-i]] or dic[b[n-1-i]])
                if tmp and carry:
                    res = "0" + res
                else:
                    res = str((tmp or carry)) + res
                    carry = 0
          
            i += 1
            
        if carry:
            res = str(carry) + res
        return res
```