My 8ms c++ solution very easy to understand


  • 0
    J
     class Solution {
     public:
     bool isValidSerialization(string preorder) {
    	int size = preorder.size();
        int finish_size;
        if(preorder=="#")
        {
            finish_size=1;
        }
        else
        {
            finish_size=-1;
        }
        int replace_num=0;
        int replace_no=-1;
        for(int i=0;i<size;i++)
    	{
    		if(preorder[i]!=',' && preorder[i]!='#')
    		{
    			if(replace_num==0)
    			{
    				replace_no=i;
    			}
    			replace_num++;
    		}
    		if(preorder[i]==','||i==size-1)
    		{
    			if(replace_num>1)
    			{
    				preorder.replace(replace_no,replace_num,"0");
    				i=replace_no;
    				size=preorder.size();
    			}
    			replace_num=0;
    			replace_no=-1;
    		}
    	}
        for(int i=0;i<size-4;)
        {
            if(preorder[i]!='#'&&preorder[i+2]=='#'&&preorder[i+4]=='#')
            {
                preorder.replace(i,5,"#");
            }
            i+=2;
    		size=preorder.size();
            if(i>=size-4)
            {
            	if(size==finish_size)
            	{
               		break;
            	}
                i=0;
                finish_size=size;
            }
        }
        if(finish_size==1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    };

  • 0
    Z
    class Soluntion {
    public:
           bool isValidSerialization(string preorder) {
           int len=preorder.length();
           if(len==0||preorder=="#") return true;
           int start=0,pos;
           stack<string> Stack;
           while(preorder.length()>0) {
               pos=preorder.find(',');
               string next;
               if(pos==-1) pos=start+preorder.length();
               next=preorder.substr(start,pos-start);
               if(preorder.length()>pos)
                    preorder=preorder.substr(pos+1);
               else preorder="";
               if(next=="#") {
                    while(!Stack.empty()&&Stack.top()=="#") {
                        Stack.pop();
                        if(!Stack.empty())
                            Stack.pop();
                    }
               if(Stack.empty()&&preorder.length()>0) return false;
               Stack.push("#");
            }
            else Stack.push(next);
          }
            if(Stack.size()==1&&Stack.top()=="#") return true;
            else return false;
         }      
    }

Log in to reply
 

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