I've recently solved the "UTF-8 Validation" LeetCode problem:
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
For 1-byte character, the first bit is a 0, followed by its unicode code.
For n-bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.
This is how the UTF-8 encoding would work:
Char. number range | UTF-8 octet sequence (hexadecimal) | (binary) --------------------+--------------------------------------------- 0000 0000-0000 007F | 0xxxxxxx 0000 0080-0000 07FF | 110xxxxx 10xxxxxx 0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx 0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
Given an array of integers representing the data, return whether it is a valid utf-8 encoding.
Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.
Example 1:
data = [197, 130, 1]
, which represents the octet sequence:11000101 10000010 00000001
.Return true. It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Example 2:
data = [235, 140, 4]
, which represented the octet sequence:11101011 10001100 00000100
.Return false. 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.
The code works and was accepted by the OJ:
NUMBER_OF_BITS_PER_BLOCK = 8
MAX_NUMBER_OF_ONES = 4
class Solution(object):
def validUtf8(self, data):
"""
:type data: List[int]
:rtype: bool
"""
index = 0
while index < len(data):
number = data[index] & (2 ** 7)
number >>= (NUMBER_OF_BITS_PER_BLOCK - 1)
if number == 0: # single byte char
index += 1
continue
# validate multi-byte char
number_of_ones = 0
while True: # get the number of significant ones
number = data[index] & (2 ** (7 - number_of_ones))
number >>= (NUMBER_OF_BITS_PER_BLOCK - number_of_ones - 1)
if number == 1:
number_of_ones += 1
else:
break
if number_of_ones > MAX_NUMBER_OF_ONES:
return False # too much ones per char sequence
if number_of_ones == 1:
return False # there has to be at least 2 ones
index += 1 # move on to check the next byte in a multi-byte char sequence
# check for out of bounds and exit early
if index >= len(data) or index >= (index + number_of_ones - 1):
return False
# every next byte has to start with "10"
for i in range(index, index + number_of_ones - 1):
number = data[i]
number >>= (NUMBER_OF_BITS_PER_BLOCK - 1)
if number != 1:
return False
number >>= (NUMBER_OF_BITS_PER_BLOCK - 1)
if number != 0:
return False
index += 1
return True
I've always being struggling to remember the bit manipulation tricks and tried to solve this problem without looking them up - hence, I think the code is overloaded with left and right shifts and power of two multiplications.
Am I overcomplicating the problem? What would you improve in the proposed solution? Is there a better way?