Java 7ms O(n) solution using bit manipulation with explanation


  • 0
    J

    Thanks to the idea from http://bookshadow.com/weblog/2016/09/04/leetcode-utf-8-validation/

    I wrote the Java version.

    The basic idea is:

    1. First determine if a n-bytes character start with '0', '110', '1110' or '11110' and find out n.
    2. Check if the following n-1 bytes start with '10'.
    3. Do the same thing to next character until the end of the array data.
    public class Solution {
        public boolean validUtf8(int[] data) {
            int[] masks = new int[]{0x0, 0x80, 0xE0, 0xF0, 0xF8};
            int[] bits = new int[]{0x0, 0x0, 0xC0, 0xE0, 0xF0};
            int start = 0;
            while(start < data.length) {
                int n;
                // start from a character
                // determine its number of bytes (n-bytes) 
                for(n = 4; n >= 0; n--) {
                    if((data[start] & masks[n]) == bits[n]) break;
                }
                // if not beginning with '0', '110', '1110', '11110'
                // or not have enough length
                // return false
                if(n == 0 || start + n > data.length ) return false;
                for(int j = 1; j < n; j++) {
                    // check if followed by n-1 bytes beginning with '10'.
                    if((data[start+j] & 0xC0) != 0x80) return false;
                }
                // continue with next character
                start += n;
            }
            return true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.