1
class Solution:
2
    def validUtf8(self, data: List[int]) -> bool:
3
        # Keep track of how many continuation bytes are left
4
        # Start at 0 since we are not expecting any continuation bytes at the beginning.
5
        cont_bytes_left = 0
6
        for byte in data:
7
            if cont_bytes_left == 0:
8
                # If we don't expect any continuation bytes
9
                # then there are 4 valid case for the current byte
10
                # byte >> 5 gives us the first 3 bits (8 bits - 5 = 3).
11
                if byte >> 5 == 0b110:
12
                    # After seeing a byte that starts with 110,
13
                    # we expect to see one continuation byte
14
                    cont_bytes_left = 1
15
                elif byte >> 4 == 0b1110:
16
                    cont_bytes_left = 2
17
                elif byte >> 3 == 0b11110:
18
                    cont_bytes_left = 3
19
                # finally if the first bit isn't 0 then it's invalid
20
                elif byte >> 7 != 0:
21
                    return False
22
            else:
23
                # If we are expecting a continuation byte there is only one valid case.
24
                # It's invalid if the continuation byte doesn't start with 10
25
                if byte >> 6 != 0b10:
26
                    return False
27
                cont_bytes_left -= 1
28

29
        # Only valid if we aren't expecting any more continuation bytes
30
        return cont_bytes_left == 0