Java O(n) Solution 7ms purely using Bit manipulation, '&' and ' | ', with detail comments


  • 0
    Z
    public boolean validUtf8(int[] data) {
    	if(data == null){
    		return true;
    	}
    	int count = 0;
    	
    	//128, 7
    	//64, 6
    	//32, 5
    	//16, 4
    	
    	for(int i = 0; i < data.length; i++){
    		if(count == 0){
    			
    			//'0...'
    			if((data[i] | 128) == 128){
    				continue;
    			}
    			
    			//'10'
    			if((data[i] & 128) == 128 && (data[i] & 64) == 0){
    				return false;
    			}
    			//'11...10'
    			if((data[i] & 128) == 128){
    				if(data.length == 1){
    					return false;
    				}
    				if((data[i] & 64) == 64){
    					count++;
    					if((data[i] & 32) == 32){
    						count++;
    						if((data[i] & 16) == 16){
    							count++;
    						}
    					}
    				}
    			}
    		}
    		
    		else{//count > 0
    			//'10'
    			if((data[i] & 128) == 128 && (data[i] & 64) == 0){
    				count--;
    			}
    			//'11...1' or "0..."
    			else{
    				return false;
    			}
    		}
    	}
    	return true;
    }

Log in to reply
 

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