Share my 4ms cpp solution with explanation


  • 0
    Z

    There are 2 rules that ensure the preorder serialization is valid:

    1, For the whole serialization, the number of '#' is always equal to the number of digits plus 1;

    2, From the start, the number of digits should not be smaller than the number of '#' until to the last element.

    Sorry for my poor English, here is the code.

    class Solution {
    public:
    
    bool isValidSerialization(string preorder) {
    	
        if(preorder.length()==0)
    		return 1;
    	
        int valCnt = 0, sentinelCnt = 0;
    	if(preorder[0]=='#')
    		sentinelCnt++;
    	else
    		valCnt++;
    	
    	for(int i=1;i<preorder.length();i++){
    		if(preorder[i-1]==','){
    			if(preorder[i] == '#')
    				sentinelCnt++;
    			else
    				valCnt++;
    		    
    		}
    		if(sentinelCnt>valCnt&&i<preorder.length()-1)
    		        return 0;
    	}
    
    	return valCnt==sentinelCnt-1;
    }
    };

Log in to reply
 

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