393. UTF-8 Validation

Question

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.

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.

Solution

位运算，循环更新UTF头部的位置start。
getByte()方法用来计算位数。
check()方法用来检查从start+1开始直到位数结束是否二进制位数以10开头。
isStartWith10()方法使用掩码判断二进制是否以10开头。

Code

class Solution {
    int[] dt;
    final int MASK = 0b11000000;
    public boolean validUtf8(int[] data) {
        dt = data;
        int start = 0;
        
        while(start < data.length){
            int bit = getByte(start);
            if(bit == -1 || start + bit > data.length) return false;
            if(!check(start, bit)) return false;
            start += bit;
        }
        return true;
    }
    
    private int getByte(int start){
        int bit = 5;
        for(int i = 0; i < 8; i++){
            if((dt[start] & 1) == 0) bit = 7 - i;
            dt[start] >>= 1;
        }
        if(bit == 0) return 1;
        else if(bit == 1 || bit > 4) return -1;
        else return bit;
    }
    
    private boolean check(int start, int bit){
        for(int i = start + 1; i < start + bit; i++) if(!isStartWith10(dt[i])) return false;
        return true;
    }
    
    private boolean isStartWith10(int num){
        return (num & MASK) == 0b10000000;
    }
}