Problem of The Day: 1-bit and 2-bit Characters

Problem Statement

leetcode problem link

Brute Force [Accepted]

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        valid = {'0', '10', '11'}
        s = ''.join(str(x) for x in bits)
        curr = ''
        for i in range(len(s)):
            curr += s[i]
            if i == len(s) - 1:
                if len(curr) > 1:
                    return False
                if curr == '1':
                    return False
                return True
            if curr in valid:
                curr = ''

Editorial

Approach 1: Increment Pointer

class Solution(object):
    def isOneBitCharacter(self, bits):
        i = 0
        while i < len(bits) - 1:
            i += bits[i] + 1
        return i == len(bits) - 1

Approach 2: Greedy

class Solution(object):
    def isOneBitCharacter(self, bits):
        parity = bits.pop()
        while bits and bits.pop(): parity ^= 1
        return parity == 0