My solution using stack


  • 2
    Y

    Solution:
    At the first glance, I have no idea about the problem. So I decided to simulate some cases to find whether there are some regulations. After trying several cases I found that the value before two consecutive '#'s should be a leaf and there are two consecutive '#'s after a leaf. So I think out a solution using stack.

    Here is the steps of the algorithm:

    1)push a '*' when we encounter a number;

    2)push a '#' when we encounter a '#',

    then judge whether the top two elements in the stack are '#', -------------- question 1

    if yes for question 1,

    judge whether the third element is '*' ---------------- question 2

    if yes for question 2, pop the top three element, then push a '#'.

    if no for question 2, then return false.

    if no for question 1, then continue.

    In the end, if there is only one element in the stack and it is '#', then return true, else return false.

    This algorithm runs in O(n) time complexity and O(n) space complexity.

    Code:

    class Solution {  
    public:  
        bool isValidSerialization(string preorder) {  
            stack<char>stk;  
            int i,len=preorder.length();  
            for(i=0;i<len;i++)  
            {  
                if(isdigit(preorder[i]))  
                {  
                    while(i<len&&isdigit(preorder[i]))  
                    {  
                        i++;  
                    }  
                    i--;  
                    stk.push('*');  
                }  
                else if(preorder[i]=='#')  
                {  
                    stk.push('#');  
                    while(stk.size()>=2&&stk.top()=='#')  
                    {  
                        stk.pop();  
                        if(stk.top()=='#')//get the last two '#', change '*' to '#'  
                        {  
                            stk.pop();  
                            if(stk.empty())return false;  
                            if(stk.top()=='#')return false;  
                            stk.pop();  
                            stk.push('#');  
                        }  
                        else  
                        {  
                            stk.push('#');  
                            break;  
                        }  
                    }  
                }  
            }  
              
            return stk.size()==1&&stk.top()=='#';  
        }  
    };

Log in to reply
 

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