Mind palace

some thoughts

0%

393. UTF-8 Validation

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

O(n) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool validUtf8(vector<int>& data) {
        int cnt = 0;
        for (int x : data) {
            if (cnt == 0) { // cnt为0说明开始检查一个新的字符，先检查高8位
                if ((x >> 5) == 0b110) {
                    cnt = 1; // 对『每一个新的字符』初始化cnt
                } else if ((x >> 4) == 0b1110) {
                    cnt = 2;
                } else if ((x >> 3) == 0b11110) {
                    cnt = 3;
                } else if (x >> 7) return false;
            } else { // 再检查低8位
                if ((x >> 6) != 0b10) return false;
                --cnt; // 更新cnt
            }
        }
        return cnt == 0; // 最后cnt必须为0
    }
};

O(n) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    bool validUtf8(vector<int>& data) {
        int n = data.size();
        for (int i = 0; i < n;) {
            if (!isValid(data, i)) return false;
        }
        return true;
    }

    bool isValid(const vector<int> &data, int &i) {
        int n = data.size();
        int j = 0;
        if (0 <= data[i] && data[i] <= 127) {
            j = i + 1;
        } else if (192 <= data[i] && data[i] <= 223) {
            if (i + 1 >= n) return false;
            j = i + 2;
        } else if (224 <= data[i] && data[i] <= 239) {
            if (i + 2 >= n) return false;
            j = i + 3;
        } else if (240 <= data[i] && data[i] <= 247) {
            if (i + 3 >= n) return false;
            j = i + 4;
        } else {
            return false;
        }
        ++i;
        for (; i < j; ++i) {
            if (data[i] < 0x0080 || data[i] > 0x00BF) return false;
        }
        return true;
    }
};