1-bit and 2-bit Characters LeetCode solution in Python

1
# Dev: Chumicat
2
# Date: 2019/11/30
3
# Submission: https://leetcode.com/submissions/detail/282638543/
4
# (Time, Space) Complexity : O(n), O(1)
5

6

7
class Solution:
8
    def isOneBitCharacter(self, bits: List[int]) -> bool:
9
        """
10
        :type bits: List[int]
11
        :rtype: bool
12
        """
13
        # Important Rules:
14
        # 1. If bit n is 0, bit n+1 must be a new char
15
        # 2. If bits end with 1, last bit must be a two bit char
16
        #    However, this case had been rejected by question
17
        # 3. If 1s in row and end with 0,
18
        #    we can use count or 1s to check last char
19
        #    If count is even, last char is "0"
20
        #    If count is odd,  last char is "10"
21
        # Strategy:
22
        # 1. We don't care last element, since it must be 0.
23
        # 2. We check from reversed, and count 1s in a row
24
        # 3. Once 0 occur or list end, We stop counting
25
        # 4. We use count to determin result
26
        # 5. Since we will mod count by 2, we simplify it to bool
27
        ret = True
28
        for bit in bits[-2::-1]:
29
            if bit:
30
                ret = not ret
31
            else:
32
                break
33
        return ret