# 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`n`

bits are all one’s, the`n + 1`

bit is`0`

, followed by`n - 1`

bytes with the most significant`2`

bits being`10`

.

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:trueExplanation: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:falseExplanation: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 * 10`

^{4}`0 <= 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