Table of Contents
UTF-8 Validation – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Given an integer array data representing the data, return whether it is a valid UTF-8 encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters).
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
- For a 1-byte character, the first bit is a
0, followed by its Unicode code. - For an n-bytes character, the first
nbits are all one’s, then + 1bit is0, followed byn - 1bytes with the most significant2bits being10.
This is how the UTF-8 encoding would work:
Number of Bytes | UTF-8 Octet Sequence
| (binary)
--------------------+-----------------------------------------
1 | 0xxxxxxx
2 | 110xxxxx 10xxxxxx
3 | 1110xxxx 10xxxxxx 10xxxxxx
4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
x denotes a bit in the binary form of a byte that may be either 0 or 1.
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:
Input: data = [197,130,1] Output: true Explanation: 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 2:
Input: data = [235,140,4] Output: false Explanation: 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 * 1040 <= data[i] <= 255
C++ UTF-8 Validation LeetCode Solution
class Solution {
public:
bool validUtf8(vector<int>& data) {
int count = 0;
for (auto c : data) {
if (count == 0) {
if ((c >> 5) == 0b110) count = 1;
else if ((c >> 4) == 0b1110) count = 2;
else if ((c >> 3) == 0b11110) count = 3;
else if ((c >> 7)) return false;
} else {
if ((c >> 6) != 0b10) return false;
count--;
}
}
return count == 0;
}
};
Java UTF-8 Validation LeetCode Solution
public boolean validUtf8(int[] data) {
if(data==null || data.length==0) return false;
boolean isValid = true;
for(int i=0;i<data.length;i++) {
if(data[i]>255) return false; // 1 after 8th digit, 100000000
int numberOfBytes = 0;
if((data[i] & 128) == 0) { // 0xxxxxxx, 1 byte, 128(10000000)
numberOfBytes = 1;
} else if((data[i] & 224) == 192) { // 110xxxxx, 2 bytes, 224(11100000), 192(11000000)
numberOfBytes = 2;
} else if((data[i] & 240) == 224) { // 1110xxxx, 3 bytes, 240(11110000), 224(11100000)
numberOfBytes = 3;
} else if((data[i] & 248) == 240) { // 11110xxx, 4 bytes, 248(11111000), 240(11110000)
numberOfBytes = 4;
} else {
return false;
}
for(int j=1;j<numberOfBytes;j++) { // check that the next n bytes start with 10xxxxxx
if(i+j>=data.length) return false;
if((data[i+j] & 192) != 128) return false; // 192(11000000), 128(10000000)
}
i=i+numberOfBytes-1;
}
return isValid;
}
Python 3 UTF-8 Validation LeetCode Solution
def check(nums, start, size):
for i in range(start + 1, start + size + 1):
if i >= len(nums) or (nums[i] >> 6) != 0b10: return False
return True
class Solution(object):
def validUtf8(self, nums, start=0):
while start < len(nums):
first = nums[start]
if (first >> 3) == 0b11110 and check(nums, start, 3): start += 4
elif (first >> 4) == 0b1110 and check(nums, start, 2): start += 3
elif (first >> 5) == 0b110 and check(nums, start, 1): start += 2
elif (first >> 7) == 0: start += 1
else: return False
return True
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
