Java O(n) time, O(1) space AC solution, concise and easy to understand


  • 0
    H
    public class Solution {
        // time O(n), n is the length of data, space O(1)
        public boolean validUtf8(int[] data) {
            int index = 0;
            while (index < data.length) {
                // how many 1 before 0 for this data
                int prefixOneNumber = prefixOneNumber(data[index]);
                if (prefixOneNumber ==  0) {
                    // type with pattern "0xxxxxxx"
                    index++;
                } else if (prefixOneNumber == 1 || prefixOneNumber > 4) {
                    // types with pattern "11111xxx" are not valid
                    // types with pattern "10xxxxxx" are handled at next branch, anyone else are invalid
                    return false;
                } else {
                    // valid pattern "10xxxxxx" these follows pattern like "1111xxxx" are handled here.
                    index++;
                    prefixOneNumber--;
                    while (prefixOneNumber > 0) {
                        if (index >= data.length || prefixOneNumber(data[index]) != 1) {
                            return false;
                        }
                        index++;
                        prefixOneNumber--;
                    }
                }
            }
            return true;
        }
        /**
         * how many 1 at the front of 0 for each data number
         * @param int: data number
         * @return int: the number of 1
         */
        private int prefixOneNumber(int data) {
            int count = 0;
            int nbit = (1 << 7);
            while ((nbit & data) == nbit && count <= 4) {
                count++;
                nbit = (nbit >> 1);
            }
            return count;
        }
    }
    

Log in to reply
 

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