LeetCode with Python: 717. 1-bit and 2-bit Characters

Description

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11). Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

Main Idea

We can directly tell the answer in 3 cases: [1, 0], [1, 1] ,and [0]. Hence we can use the recursion solution to turn the bits to these cases. If bits start with number 0, then we decode it’s a 1-bit character, it’s a 2-bit character otherwise.

Solution