Skip to content

LeetCode: 393-UTF-8 Validation 解題紀錄

Last Updated on 2022-09-13 by Clay

題目

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:

  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 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: 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 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 * 104
  • 0 <= data[i] <= 255

本題是讓我們驗證接收到的 UTF-8 編碼是否『有效』。UTF-8 編碼皆為 8 位元,可以用一個整數來表達(也就是題目真正的輸入:正整數)。

  • 僅有一個位元組的字元,開頭會是 0,可能表現形式為 0xxxxxxx
  • 兩個位元組:110xxxxx 10xxxxxx
  • 三個位元組:1110xxxx 10xxxxxx 10xxxxxx
  • 四個位元組:11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

不會有五個位元組的表示形式存在,這一點需要考慮進去。而只要不是僅有一個位元組的表示,除了開頭的二進制表示開頭會有代表幾個位元組的 1's,其後的位元組全都是 10xxxxxx 這樣的表示形式。

也就是說,假設我們的四位元組表示成:

11110xxx 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx 0xxxxxxx 10xxxxxx


這樣可是無效的 UTF-8 編碼表示。多個位元組的表現形式後頭一定要接同樣的 10 開頭的 11110xxx 表示。

也要注意的是,如果一個 UTF-8 的字元表示結束了,後面當然是可以再繼續接其他字元的。這點我一開始土法煉鋼時就不小心搞錯了。

110xxxxx 10xxxxxx 0xxxxxxx


像是這樣,兩個位元組的字元表示完了,但後面當然可以再接一個單個位元組的字元表達。這是合法的 UTF-8 字串。


解題思路

我一開始很理所當然地暴力把數值轉成位元組的字串,然后計算第一個位元組開頭的 1 的數量,把後頭應該要接著的位元組數量儲存,再判斷後面的位元組是否為 10xxxxxx 的表達方式,直到符合最開頭的位元組數量,再進入下一個字元的判斷...... 依此類推,直到結束。

後來解完後,看了下討論區,發現厲害的高手們都是直接用位元操作,我這才恍然大悟...... 只能說自己對於位元操作實在太不熟了,好在被提示過後還是自己摸索出了解題法,基本上就是改進了第一個土法煉鋼版本的判斷過程,變得更有效率。

兩種解法我都一併紀錄在下方。


Brute Force

C++ 解題紀錄

class Solution {
public:
    bool validUtf8(vector<int>& data) {
        // Init
        int currMaxN = 0;

        // Determined        
        for (int i=0; i<data.size(); ++i) {
            int currN = 0;
            string s = bitset<8>(data[i]).to_string();
                        
            // Count 1's
            for (int j=0; j<s.size(); ++j) {
                if (s[j] == '1') {
                    ++currN;
                }
                else {
                    break;
                }
            }
                        
            if (currMaxN == 0) {
                if (currN == 1) {
                    return false;
                }
                else if (currN > 1) {
                    currMaxN = currN - 1;
                }
            }
            else if (currMaxN > 0) {
                if (currN == 1) {
                    --currMaxN;
                }
                else {
                    return false;
                }
            }
            
            if (currMaxN >= 4) {
                return false;
            }
        }
        
        return currMaxN == 0;
    }
};



Python 解題紀錄

Python 的 bin() 轉成的字串比較麻煩的是,如果像是 1 這樣的數值會自動省略掉一堆 0,導致很難透過字串判斷,需要另外再寫規則把 0 填充回來。

class Solution:
    def validUtf8(self, data: List[int]) -> bool:
        # Init
        curr_n = 0
        data = map(bin, data)

        # Determined
        for byte in data:
            byte = byte[2:].zfill(8)
            
            if curr_n == 0:
                if byte[:3] == "110":
                    curr_n = 1
                elif byte[:4] == "1110":
                    curr_n = 2
                elif byte[:5] == "11110":
                    curr_n = 3
                elif byte[0] != "0":
                    return False
            else:
                if byte[:2] == "10":
                    curr_n -= 1
                else:
                    return False
        
        return curr_n == 0




位元操作(Bit Manipulation)

這個方法基本上也是在判斷開頭的 1 數量,不過直接透過位元操作取前幾位元判斷顯然比操作字串快得多。除此之外,整個程式的流程沒有太大改變,就是優化了判斷過程,所以速度是好上挺多的。

C++ 解題紀錄

class Solution {
public:
    bool validUtf8(vector<int>& data) {
        // Init
        int currMaxN = 0;

        // Determined        
        for (int i=0; i<data.size(); ++i) {
            // Count 1's
            if (currMaxN == 0) {
                if (data[i] >> 5 == 0b110) {
                    currMaxN = 1;
                }
                else if (data[i] >> 4 == 0b1110) {
                    currMaxN = 2;
                }
                else if (data[i] >> 3 == 0b11110) {
                    currMaxN = 3;
                } 
                else if (data[i] >> 7 != 0) {
                    return false;
                }
            }
            else {
                if (data[i] >> 6 == 0b10) {
                    --currMaxN;
                }
                else {
                    return false;
                }
            }
        }
        
        return currMaxN == 0;
    }
};



Python 解題紀錄

class Solution:
    def validUtf8(self, data: List[int]) -> bool:
        # Init
        curr_n = 0

        # Determined
        for byte in data:            
            if curr_n == 0:
                if byte >> 5 == 0b110:
                    curr_n = 1
                elif byte >> 4 == 0b1110:
                    curr_n = 2
                elif byte >> 3 == 0b11110:
                    curr_n = 3
                elif byte >> 7:
                    return False
            else:
                if byte >> 6 == 0b10:
                    curr_n -= 1
                else:
                    return False
        
        return curr_n == 0

References


Read More

Leave a Reply