Problem statement

https://leetcode.com/problems/utf-8-validation/

Solution

For number we need to be able to evaluate how many leading ones it has. It can be 0, 1, 2, 3 or 4. Then we just process our numbers: if we see 0, we continue. If we see 2, next one should be 1. If we see 3, next two should be 1. If we see 4, next three should be 1. If we see 1 or more than 5, we return False immedietly.

Complexity

Time omplexity is O(n), space complexity is O(1).

Code

class Solution:
    def validUtf8(self, data):
        def NB(num):
            n_bytes, mask = 0, 1<<7
            while mask & num:
                n_bytes += 1
                mask = mask >> 1
            return n_bytes
        
        i = 0
        while i < len(data):
            T = NB(data[i])
            if T == 0:
                i += 1
            elif 2 <= T <= 4:
                for j in range(1, T):
                    if i + j >= len(data) or NB(data[i+j]) != 1:
                        return False
                i += T
            else: return False
            
        return True