UTF-8 Validation
Real-world version: Checking a Packed Octet StreamThe statement here is our own: the same inputs, outputs and technique.
A stream stream holds whole numbers, and only the lowest eight bits of each one count: those bits make up one octet of data.
Characters are packed into one to four octets by this scheme:
- A one-octet character has a top bit of
0, so the octet reads0xxxxxxx. - A character of
noctets, withnbetween2and4, opens with an octet whose topnbits are all1followed by a0, and every octet after that reads10xxxxxx.
So two octets read 110xxxxx 10xxxxxx, three read 1110xxxx 10xxxxxx 10xxxxxx, and four read 11110xxx followed by three octets of 10xxxxxx.
Return true when the whole stream is packed correctly under that scheme.
Examples
Example 1
- Input
- stream = [224, 160, 128]
- Output
- true
The first octet opens with 1110, promising three octets, and the two after it both open with 10.
Example 2
- Input
- stream = [197]
- Output
- false
The octet opens with 110 and so promises a second octet, but the stream ends there.
Example 3
- Input
- stream = [128]
- Output
- false
The octet opens with 10, which can only follow a leading octet, so it cannot start a character at all.
Constraints
- 1 <= stream.length <= 2 * 10^4
- 0 <= stream[i] <= 255
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def valid_utf8(stream: list[int]) -> bool:public boolean validUtf8(int[] stream)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's