UTF-8 编码验证

难度: Medium

给定一个表示数据的整数数组 data ，返回它是否为有效的 UTF-8 编码。

UTF-8 中的一个字符可能的长度为 1 到 4 字节，遵循以下的规则：

对于 1 字节 的字符，字节的第一位设为 0 ，后面 7 位为这个符号的 unicode 码。
对于 n 字节 的字符 (n > 1)，第一个字节的前 n 位都设为1，第 n+1 位设为 0 ，后面字节的前两位一律设为 10 。剩下的没有提及的二进制位，全部为这个符号的 unicode 码。

这是 UTF-8 编码的工作方式：

      Number of Bytes  |        UTF-8 octet sequence
                       |              (binary)
   --------------------+---------------------------------------------
            1          | 0xxxxxxx
            2          | 110xxxxx 10xxxxxx
            3          | 1110xxxx 10xxxxxx 10xxxxxx
            4          | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x 表示二进制形式的一位，可以是 0 或 1。

注意：输入是整数数组。只有每个整数的 最低 8 个有效位 用来存储数据。这意味着每个整数只表示 1 字节的数据。

示例 1：

输入：data = [197,130,1]
输出：true
解释：数据表示字节序列:11000101 10000010 00000001。
这是有效的 utf-8 编码，为一个 2 字节字符，跟着一个 1 字节字符。

示例 2：

输入：data = [235,140,4]
输出：false
解释：数据表示 8 位的序列: 11101011 10001100 00000100.
前 3 位都是 1 ，第 4 位为 0 表示它是一个 3 字节字符。
下一个字节是开头为 10 的延续字节，这是正确的。
但第二个延续字节不以 10 开头，所以是不符合规则的。

提示:

1 <= data.length <= 2 * 10⁴
0 <= data[i] <= 255

Submission

运行时间: 31 ms

内存: 16.4 MB

class Solution:
    def validUtf8(self, data: List[int]) -> bool:
        tail_flag = 0
        for byte in data:
            if tail_flag == 0:
                if 0b10000000 & byte == 0:
                    continue
                else:
                    if 0b01000000 & byte == 0:
                        # 10xx xxxx
                        return False
                    if 0b00100000 & byte == 0:
                        # 110x xxxx
                        tail_flag = 1
                    elif 0b00010000 & byte == 0:
                        # 1110 xxxx
                        tail_flag = 2
                    elif 0b00001000 & byte == 0:
                        # 1111 0xxx:
                        tail_flag = 3
                    else:
                        # 1111 1xxx
                        return False
            elif tail_flag > 0:
                if 0b11000000 & byte == 0b10000000:
                    tail_flag -= 1
                else:
                    return False
            else:
                return False
        return tail_flag == 0

Explain

这个题解采用迭代的方式遍历字节数组，对每个字节进行分析。如果当前字节是一个 UTF-8 编码的开始字节，根据其前缀的 1 的个数确定后续应该有几个字节（用 tail_flag 变量表示）。如果当前字节是一个后续字节，则检查其前两位是否为 10。迭代结束后，如果 tail_flag 为 0，说明所有字节都符合 UTF-8 编码规则。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def validUtf8(self, data: List[int]) -> bool:
        tail_flag = 0
        for byte in data:
            if tail_flag == 0:
                if 0b10000000 & byte == 0:
                    # 0xxx xxxx，单字节字符
                    continue
                else:
                    if 0b01000000 & byte == 0:
                        # 10xx xxxx，非法的起始字节
                        return False
                    if 0b00100000 & byte == 0:
                        # 110x xxxx，双字节字符
                        tail_flag = 1
                    elif 0b00010000 & byte == 0:
                        # 1110 xxxx，三字节字符
                        tail_flag = 2
                    elif 0b00001000 & byte == 0:
                        # 1111 0xxx，四字节字符
                        tail_flag = 3
                    else:
                        # 1111 1xxx，非法字节
                        return False
            elif tail_flag > 0:
                if 0b11000000 & byte == 0b10000000:
                    # 10xx xxxx，合法的后续字节
                    tail_flag -= 1
                else:
                    # 非法的后续字节
                    return False
            else:
                # tail_flag 小于 0，非法情况
                return False
        # 确保所有字节都被处理完
        return tail_flag == 0

Explore

在UTF-8编码中，一个字符的起始字节和后续字节的格式不同。起始字节的最高位的连续1的个数决定了该字符占用的字节数。例如，单字节字符以0开头，双字节字符以110开头，三字节字符以1110开头，四字节字符以11110开头。相应的位运算检测就是通过按位与操作（&）与特定的掩码比较来实现的。例如，对于双字节字符，我们检查是否符合110xxxxx的模式，可以使用掩码0b11100000（即224）来检查前三位是否为110，并确保第四位为0（通过0b00010000即16检查）。

UTF-8编码规则中，多字节字符的起始字节的前几位是固定的，这些位标志了后续字节数。例如，一个两字节字符的起始字节以110开头，三字节字符以1110开头，四字节字符以11110开头。通过检查这些位，我们可以确定字符所需的字节总数。检查除第一位之外的其余位是否为0是为了验证后续的位模式是否符合预期的格式。这样的检查确保了解码过程的正确性，防止解释错误的数据格式。

我的算法通过维护一个tail_flag变量来记录一个多字节字符还需要多少后续字节。如果在处理完所有输入字节后tail_flag不为0，这意味着数据不完整，即某个多字节字符的后续字节没有完全出现。在这种情况下，算法会返回False，表示输入数据不是有效的UTF-8编码。

是的，这种设计考虑了起始字节和后续字节的合法性。起始字节必须符合UTF-8的编码规则，后续字节必须以10开头。如果不符合这些规则，数据显然是错误的，算法会立即返回False。除此之外，算法还处理了数据不完整的情况。虽然这些检查覆盖了大多数错误情况，但是还有一些极端情况，如输入数据为空或数据异常大等边缘情况，这些可能需要在实际应用中额外处理。