O(n) solution using Java


  • 3
    S
    public class Solution {
        public boolean validUtf8(int[] data) {
            int n = data.length;
            if (n == 0) return true;
            int skip = 0b10000000;
            int check = 0;
            for (int i = 0; i < data.length; i++) {
                if (check > 0) {
                    if ((data[i] & skip) == skip) check--;
                    else return false;
                } else {
                    check = getOneBitCountFromHead(data[i]);
                    if (check < 0) return false;
                }
            }
            return check == 0;
        }
        private int getOneBitCountFromHead(int num) {
            if ((num & 0b11110000) == 0b11110000) return 3;
            if ((num & 0b11100000) == 0b11100000) return 2;
            if ((num & 0b11000000) == 0b11000000) return 1;
            if ((num & 0b10000000) == 0b10000000) return -1; //error
            return 0;
        }
    }
    

  • 0

    @sungyong.an

    the skip = 0b10000000
    if data = 0b11111111
    skip & data = 10000000 which is equal to skip

    However, data is not a valid format of 10xxxxxx


  • 0
    B

    I like your coding style and well organized solution.

    But for this line

    if ((data[i] & skip) == skip) check--;
    

    I agree with @yubad2000 . Since the second significant bit of skip is 0, which will ignore whether the second significant bit of data[i], it might return true even if data[i] is 11xxxxxx.

    I would suggest if((data[i] >>> 6) == 0b10)


  • 0
    I

    Thanks for sharing your idea, I also like your coding style, which is much clear than other topics with more votes. As pointed out by others above, there might be potential issue with your code, I'm attaching the fixed version:

    public class Solution {
        public boolean validUtf8(int[] data) {
            if (data == null || data.length == 0) return false;
            
            int idx = 0;
            int len = data.length;  
            while (idx < len) {
                int follows = getFollows(data[idx++]);
                if (follows == -1) return false;
                
                for (int i = 0; i < follows; i++) {
                    if (idx >= len) {
                        return false;
                    } else {
                        if (!isFollowed(data[idx++])) {
                            return false;
                        }
                    }
                }
            }
            return true;
        }
        
        /* Return the number of segment/segments that needs/need to be followed */
        private int getFollows(int num) {
            if ((num & 0b10000000) == 0) return 0;  // use parenthesis for &, due to its low priority
            else if ((num & 0b11100000) == 0b11000000) return 1;
            else if ((num & 0b11110000) == 0b11100000) return 2;
            else if ((num & 0b11111000) == 0b11110000) return 3;
            return -1;
        }
        
        /* to check if the num starts with "10" */
        private boolean isFollowed(int num) {
            return (num & 0b11000000) == 0b10000000;
        }
    }
    

Log in to reply
 

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