one pass simple solution


  • 12
    T

    public class Solution {

    public bool ValidUtf8(int[] data) {
        int bitCount = 0;
        
        foreach(int n in data){
            
            if(n >= 192){
                if(bitCount != 0)
                    return false;
                else if(n >= 240)
                    bitCount = 3;
                else if(n >= 224)
                    bitCount = 2;
                else
                    bitCount = 1;
            }else if(n >= 128){
                bitCount--;
                if(bitCount < 0)
                    return false;
            }else if(bitCount > 0){
                return false;
            }
        }
        
        return bitCount == 0;
    }
    

    }


  • 1
    H

    Great solution! Can you please give some explanation about the logic?


  • 0
    T

    @hao32 sure.

    n >= 240 means at least 11110000 (next 3 number will at least 128) (bitCount = 3)
    224> n > 192 means at least 11000000 (next 1 number will at least 128) (bitCount = 2)
    240> n >= 224 mens at least 111000000 (next 2 number will at least 128) (bitCount = 1)

    if(any bitCount < 0)


  • 0
    W

    Hi I am not familiar with the UTF-8 rule.
    Can the element in data be bigger that 255? like 444, etc.
    Because in this case the bit count will be >= 4.


  • 0
    C

    @whglamrock If there is an element greater than 255, this method will return false as it will hit this code path.

               else if(n >= 128){
                    bitCount--;
                    if(bitCount < 0) return false;
    

    Question states A character in UTF8 can be from 1 to 4 bytes long. It can't be greater than 4.


  • 2
    N

    Added this to pass test case #48 :

            if(bitCount != 0)
                return false;
            else if(n > 247)
                return false;
    

    This is necessary since you need to return false if you have more than 4 leading 1's, i.e. more than 4 bytes.


Log in to reply
 

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