LeetCode #67 Add Binary

Easy

Problem

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.

Example 1:

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

Example 2:

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

Solution

Our approach is to iterate two list from end to start at the same time. If current index out of index, treat it as 0. At each iteration, we should handle the add up behavior and update result and the carry bit.

It’s noted that if carry bit is still 1 after iteration terminated, we have to prepend a more 1 in front of result.

Complexity

We will iterate the list which has longer length once so the time complexity is O(A+B) if A denotes to length of a and B denotes to length of b.

There is a list used to save result of adding up so space complexity is O(A+B) as well.