[LeetCode] 717. 1-bit and 2-bit Characters

 Problem : https://leetcode.com/problems/1-bit-and-2-bit-characters/

Remove the last 2 bits, then check if the remaining sequence is still valid.

If the remaining sequence is not valid, then the last character must be a one-bit character.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        
        @cache
        def helper(i):
            """
            return True is bits[:i] is a valid sequence
            """
            
            if i == 0:
                return True
            
            # bits[i-1] can be decoded as the one-bit character
            if bits[i-1] == 0 and helper(i-1):
                return True
            
            # bits[i-2]bits[i-1] can be decoded as the two-bit character
            if i - 2 >= 0 and bits[i-2] == 1:
                return helper(i-2)
            
            # bits[:i] is an invalid sequence
            return False
        
        # bits[-2] == 0 so bits[-1] must be decoded as one-bit character
        if len(bits) == 1 or bits[-2] == 0: return True
        
        # return False if the remaining sequence is still valid by removing the last 2 bits
        return not helper(len(bits) - 2)