Xác thực UTF-8 trong C++

Mô tả bài toán

Cho mảng số nguyên (0-255) đại diện cho byte stream. Kiểm tra có phải mã hóa UTF-8 hợp lệ không.

Quy tắc UTF-8:

• 1 byte: 0xxxxxxx
• 2 byte: 110xxxxx 10xxxxxx
• 3 byte: 1110xxxx 10xxxxxx 10xxxxxx
• 4 byte: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Giải thuật Duyệt một lần

1. Biến cnt = số byte tiếp theo mong đợi (byte tiếp theo phải bắt đầu bằng 10).
2. Duyệt từng byte x:
   • Nếu cnt == 0: xác định độ dài ký tự bằng bit đầu:
     • (x>>5) == 0b110 → cnt=1
     • (x>>4) == 0b1110 → cnt=2
     • (x>>3) == 0b11110 → cnt=3
     • (x>>7) != 0 → sai (không phải 1-byte hợp lệ).
   • Nếu 0: kiểm tra (x>>6) == 0b10, giảm cnt--.
3. Cuối cùng cnt == 0 thì hợp lệ.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool validUtf8(vector<int>& data) {
        int cnt = 0;
        for (int x : data) {
            if (cnt == 0) {
                if ((x >> 5) == 0b110) cnt = 1;
                else if ((x >> 4) == 0b1110) cnt = 2;
                else if ((x >> 3) == 0b11110) cnt = 3;
                else if ((x >> 7) != 0) return false;
            } else {
                if ((x >> 6) != 0b10) return false;
                cnt--;
            }
        }
        return cnt == 0;
    }
};

int main() {
    vector<int> v = {197, 130, 1};
    Solution ob;
    cout << ob.validUtf8(v); // 1 (true)
    return 0;
}

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(1).