393. UTF-8 Validation

Problem Description

Given an array of integers data representing byte data, determine if it's a valid UTF-8 encoding. UTF-8 encodes characters using 1 to 4 bytes. The rules are:

1. 1-byte character: Starts with 0 (e.g., 0xxxxxxx).
2. n-byte character (n > 1): Starts with n ones followed by a zero, then n-1 continuation bytes starting with 10 (e.g., 110xxxxx 10xxxxxx for 2-byte, 1110xxxx 10xxxxxx 10xxxxxx for 3-byte, etc.).

Each integer in data represents a single byte. The task is to check if the entire sequence forms valid UTF-8 characters.

Solution: Single Pass

This solution efficiently validates UTF-8 encoding in a single pass through the input array. It leverages bit manipulation to check the leading bits of each byte.

Algorithm:

1. Initialize a counter cnt to 0. This counter tracks the number of continuation bytes expected for a multi-byte character.

2. Iterate through each byte v in the data array:

   • If cnt > 0: We're in the middle of a multi-byte character. Check if the byte v is a valid continuation byte (starts with 10). If not, return false. Otherwise, decrement cnt.
   • If cnt == 0: We've encountered a new byte. Determine the number of bytes needed for this character based on the leading bits:
     • If the highest bit is 0 (v >> 7 == 0), it's a single-byte character (cnt = 0).
     • If the highest two bits are 110 (v >> 5 == 0b110), it's a two-byte character (cnt = 1).
     • If the highest three bits are 1110 (v >> 4 == 0b1110), it's a three-byte character (cnt = 2).
     • If the highest four bits are 11110 (v >> 3 == 0b11110), it's a four-byte character (cnt = 3).
     • Otherwise, the byte doesn't represent a valid UTF-8 start, so return false.

3. After the loop, if cnt == 0, it means all multi-byte characters were correctly completed, and the function returns true. Otherwise, it returns false.

Time Complexity: O(n), where n is the length of the data array. We iterate through the array once.

Space Complexity: O(1), as we use only a constant amount of extra space for the cnt variable.

Code Implementation

The code below shows the implementation in several programming languages:

Python:

def validUtf8(data: list[int]) -> bool:
    cnt = 0
    for v in data:
        if cnt > 0:
            if (v >> 6) != 0b10:  # Check for continuation byte
                return False
            cnt -= 1
        elif (v >> 7) == 0:  # Single-byte character
            cnt = 0
        elif (v >> 5) == 0b110:  # Two-byte character
            cnt = 1
        elif (v >> 4) == 0b1110:  # Three-byte character
            cnt = 2
        elif (v >> 3) == 0b11110:  # Four-byte character
            cnt = 3
        else:
            return False  # Invalid UTF-8 start
    return cnt == 0
 

Java:

class Solution {
    public boolean validUtf8(int[] data) {
        int cnt = 0;
        for (int v : data) {
            if (cnt > 0) {
                if ((v >> 6) != 0b10) return false;
                cnt--;
            } else if ((v >> 7) == 0) {
                cnt = 0;
            } else if ((v >> 5) == 0b110) {
                cnt = 1;
            } else if ((v >> 4) == 0b1110) {
                cnt = 2;
            } else if ((v >> 3) == 0b11110) {
                cnt = 3;
            } else {
                return false;
            }
        }
        return cnt == 0;
    }
}

C++:

class Solution {
public:
    bool validUtf8(vector<int>& data) {
        int cnt = 0;
        for (int v : data) {
            if (cnt > 0) {
                if ((v >> 6) != 0b10) return false;
                cnt--;
            } else if ((v >> 7) == 0) {
                cnt = 0;
            } else if ((v >> 5) == 0b110) {
                cnt = 1;
            } else if ((v >> 4) == 0b1110) {
                cnt = 2;
            } else if ((v >> 3) == 0b11110) {
                cnt = 3;
            } else {
                return false;
            }
        }
        return cnt == 0;
    }
};

// JavaScript, Go, TypeScript implementations would follow a similar structure. The core logic remains the same across languages.

This efficient single-pass approach ensures a linear time complexity solution for validating UTF-8 encoded data.