Solve UTF-8 Validation & Shortest Path

Question

LeetCode 393. UTF-8 Validation LeetCode 1091. Shortest Path in Binary Matrix

https://leetcode.com/problems/utf-8-validation/description/ https://leetcode.com/problems/shortest-path-in-binary-matrix/description/

UTF-8 Validation

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 UTF-8 can be from 1 to 4 bytes long, subjected to the following rules:

1. For a 1-byte character, the first bit is a 0, followed by its Unicode code.
2. For an n-bytes character, the first n bits are all ones, the (n+1)-th 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 are 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 represents 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
• Only the least significant 8 bits of each integer are used as data.

Hints

1. Track how many continuation bytes you still expect. When that counter is 0 you are reading a leading byte; otherwise you are reading a continuation byte.
2. Mask each integer with & 0xFF first, then inspect the top bits to classify it: 0xxxxxxx is a 1-byte char, 110xxxxx starts 2 bytes, 1110xxxx starts 3, 11110xxx starts 4.
3. Every continuation byte must start with 10. If a leading byte is malformed (e.g. starts with 10 or 11111), or you run out of bytes mid-character, the encoding is invalid. At the end the expected-continuation counter must be 0.

Shortest Path in Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

• All the visited cells of the path are 0.
• All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1
Explanation: The start cell is blocked.

Constraints

• n == grid.length == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1

Hints

1. Because every move has the same cost (one cell), the shortest path is found by Breadth-First Search, not DFS.
2. Movement is 8-directional, so each cell has up to 8 neighbors: the four orthogonal plus the four diagonal offsets.
3. Handle the trivial blockers first: if the start (0,0) or the end (n-1,n-1) is 1, return -1 immediately. Mark cells visited when you enqueue them (not when you dequeue) to avoid revisiting and inflating the queue.