0393. UTF-8 Validation

题目信息

题号:

0393

难度:

Medium

主题:

字节序列、UTF-8 前缀、连续字节、完整消费

原题:

LeetCode 0393

重点:

字符长度只能为 1 到 4 字节、首字节决定后续数量、连续字节必须以二进制 10 开头、序列不能残缺

题目重述

给定整数数组 data,每个整数位于 [0, 255],表示一个八位字节。判断整个字节序列是否符合题目规定的 UTF-8 编码格式:单字节字符的首位为 0;长度为 n 的多字节字符,其首字节前 n 位为 1、下一位为 0,其中 n 只能是 2、3 或 4;后续每个字节都必须以二进制前缀 10 开头。

数组长度位于 [1, 2 * 10^4]。每个字节必须恰好属于一个完整字符,不能出现孤立连续字节、声明五字节以上字符的首字节,或在数组结束时仍缺少连续字节。题目只按上述位模式验证,不要求返回解码后的字符。

自建示例

完整的三字节字符:

输入:data = [226,130,172]
输出:true
解释:226 的二进制以 1110 开头,表示还需要两个连续字节;130 和 172 都以 10 开头。

多字节字符在结尾残缺:

输入:data = [240,162,138]
输出:false
解释:240 声明一个四字节字符,但数组只提供了两个后续字节,还缺少一个连续字节。

用 remaining 表示当前字符还需几个连续字节

从左到右读取字节。若当前没有等待连续字节,则根据首字节的前缀判断字符长度:0 表示单字节,110、1110、11110 分别表示还需 1、2、3 个字节;其他前缀均非法。若正在等待,当前字节必须满足 10xxxxxx,通过后将剩余数减一。

数组结束时 remaining 必须为零,否则最后一个字符不完整;孤立的连续字节也会在 remaining == 0 时无法匹配任何首字节格式。

C++ 实现

class Solution {
public:
    bool validUtf8(std::vector<int>& data) {
        int remaining = 0;
        for (int byte : data) {
            if (remaining == 0) {
                if ((byte & 0x80) == 0) {
                    continue;
                } else if ((byte & 0xE0) == 0xC0) {
                    remaining = 1;
                } else if ((byte & 0xF0) == 0xE0) {
                    remaining = 2;
                } else if ((byte & 0xF8) == 0xF0) {
                    remaining = 3;
                } else {
                    return false;
                }
            } else {
                if ((byte & 0xC0) != 0x80) return false;
                --remaining;
            }
        }
        return remaining == 0;
    }
};

代码分析

首字节只负责建立“还需几个字节”的状态,连续字节只负责消耗状态;掩码 0xF8 也会拒绝五字节及更长前缀。每个字节只检查一次,时间复杂度为 O(n),额外空间为 O(1)。