UTF-8 Validation
Medium · Bit Manipulation · Explanation and code example
Track Expected Continuation Bytes
How it works
Inspect a leading byte’s prefix to determine whether zero, one, two, or three continuation bytes must follow. While continuation bytes remain, each byte must begin with binary 10. The input is valid only if every leading prefix is recognized and no continuation remains at the end.
Steps
- Classify each leading byte by its high bits.
- Require 10-prefixed bytes while a sequence is unfinished.
- Accept only when the expected continuation count returns to zero.
Complexity
- Time: O(n).
- Space: O(1).
Things to watch for
- Reject a continuation byte where a leading byte is required.
- Reject a truncated final sequence.
- This checks the problem’s byte-prefix rules, rather than all Unicode code-point restrictions.
Python code example
class Solution:
def validUtf8(self, data: list[int]) -> bool:
followedBytes = 0
for d in data:
if followedBytes == 0:
if (d >> 3) == 0b11110:
followedBytes = 3
elif (d >> 4) == 0b1110:
followedBytes = 2
elif (d >> 5) == 0b110:
followedBytes = 1
elif (d >> 7) == 0b0:
followedBytes = 0
else:
return False
else:
if (d >> 6) != 0b10:
return False
followedBytes -= 1
return followedBytes == 0
C++ code example
class Solution {
public:
bool validUtf8(vector<int>& data) {
int followedBytes = 0;
for (const int d : data)
if (followedBytes == 0) {
if ((d >> 3) == 0b11110)
followedBytes = 3;
else if ((d >> 4) == 0b1110)
followedBytes = 2;
else if ((d >> 5) == 0b110)
followedBytes = 1;
else if ((d >> 7) == 0b0)
followedBytes = 0;
else
return false;
} else {
if ((d >> 6) != 0b10)
return false;
--followedBytes;
}
return followedBytes == 0;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.