#393

Medium

LeetCode Problem Workspace

UTF-8 Validation

Determine if an integer array represents valid UTF-8 encoding based on its byte sequences using bit manipulation.

Problem Statement

You are given an array of integers, where each integer represents a byte of data in a potential UTF-8 encoded string. Your task is to determine whether the array is a valid UTF-8 encoding. UTF-8 encoding rules specify that a character can be 1 to 4 bytes long, with each byte adhering to specific bit patterns.

The following rules govern how a UTF-8 character is encoded: 1-byte characters start with '0', 2-byte characters start with '110' followed by '10', 3-byte characters start with '1110' followed by two '10' bytes, and 4-byte characters start with '11110' followed by three '10' bytes. Your task is to verify that each byte and its subsequent bytes adhere to these rules.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Example 2

Input: data = [197,130,1]

Output: true

data represents the octet sequence: 11000101 10000010 00000001. It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

Example 3

Input: data = [235,140,4]

Output: false

data represented the octet sequence: 11101011 10001100 00000100. The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character. The next byte is a continuation byte which starts with 10 and that's correct. But the second continuation byte does not start with 10, so it is invalid.

Constraints

1 <= data.length <= 2 * 104
0 <= data[i] <= 255

Solution Approach

Reading Each Byte

Iterate through the integer array, processing each byte. The first byte in the sequence will dictate how many continuation bytes are expected. For example, if the first byte starts with '110', then two more bytes starting with '10' should follow.

Validating Continuation Bytes

For each byte, check that the subsequent bytes start with the '10' bit pattern, which signifies a continuation byte. If any byte fails this check, return false.

Handling Byte Sequence Length

The number of continuation bytes expected is determined by the number of leading '1's in the first byte. Ensure that the correct number of continuation bytes follow the first byte based on this pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	O(1)

The time complexity depends on the final approach but generally will be O(n), where n is the length of the input array. Space complexity is O(1) as the problem can be solved in-place without extra space for data structures.

What Interviewers Usually Probe

Look for clear identification of how many continuation bytes follow each byte.
Assess understanding of bit manipulation and byte operations.
Ensure the solution handles edge cases like incomplete byte sequences.

Common Pitfalls or Variants

Common pitfalls

Failing to properly identify the number of expected continuation bytes based on the first byte's leading bits.
Misunderstanding the rules of valid continuation bytes, particularly the '10' pattern.
Incorrectly processing arrays with invalid sequences, such as bytes that don’t follow the proper encoding pattern.

Follow-up variants

Modify the problem to validate UTF-16 or UTF-32 encoding.
Introduce a larger input size to assess the solution's efficiency under heavy constraints.
Ask for an optimization to minimize space usage further.

FAQ

What are the main rules for UTF-8 encoding validation?

UTF-8 encoding has specific bit patterns: 1-byte starts with '0', 2-byte starts with '110' followed by '10', 3-byte starts with '1110' followed by '10 10', and 4-byte starts with '11110' followed by '10 10 10'.

How do I process continuation bytes in the UTF-8 validation problem?

Continuations bytes must always start with the bit pattern '10'. If any byte in the sequence doesn't follow this pattern, the encoding is invalid.

How does the number of leading ones in the first byte help in UTF-8 validation?

The number of leading ones in the first byte indicates how many continuation bytes are expected. For example, 3 leading ones mean 3 continuation bytes are required.

What is the space complexity for the UTF-8 validation problem?

The space complexity is O(1) because the solution can be implemented with a fixed amount of extra space, regardless of the input size.

Can this problem be solved using simple loops?

Yes, the problem can be solved efficiently using loops and bit manipulation to check each byte and its continuation bytes.

terminal

Solution

Solution 1: Single Pass

We use a variable $cnt$ to record the current number of bytes that need to be filled starting with $10$, initially $cnt = 0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def validUtf8(self, data: List[int]) -> bool:
        cnt = 0
        for v in data:
            if cnt > 0:
                if v >> 6 != 0b10:
                    return False
                cnt -= 1
            elif v >> 7 == 0:
                cnt = 0
            elif v >> 5 == 0b110:
                cnt = 1
            elif v >> 4 == 0b1110:
                cnt = 2
            elif v >> 3 == 0b11110:
                cnt = 3
            else:
                return False
        return cnt == 0

Continue Practicing

#421 maximum xor of two numbers in an array #318 maximum product of word lengths #473 matchsticks to square