O(N) time and space (using stack)


  • 0
    M

    I implemented using two stacks, one is for ‘(‘ and ‘’ count and other for keeping ‘’.

    1. For every ‘(‘, push stack-1 with char and count of stack-2.
    2. For every ‘*’, push to stack-2
    3. For every ‘)’, pop from stack-1 if it is not empty, else pop from stack-2. If both stacks are empty return false.
    4. Finally, pop everything from stack-1 and return false if starcount is less than stack-2 count.
    public class CharandStarCount
    {
        public char ch;
        public int startCount;
        public CharandStarCount(char ch, int cnt)
        {
            this.ch = ch;
            this.startCount = cnt;
        }
    }
    public class Solution {
        bool removeFromStack (Stack<CharandStarCount> par, Stack<char> star)
        {
            if (par.Count > 0)
            {
                 par.Pop();
                 return true;
            }
            
             if (star.Count > 0)
            {
                 star.Pop();
                 return true;
            }
            return false;
       }
       
       public bool CheckValidString(string s) {
            if (s == String.Empty || s == null)
                 return true;
            Stack<CharandStarCount> pstack = new Stack<CharandStarCount>();
            Stack<char> sstack = new Stack<char>();
            foreach(char ch in s)
            {
                switch (ch)
                {
                    case '(' :
                            CharandStarCount temp = new CharandStarCount(ch,sstack.Count);
                            pstack.Push(temp);
                            break;
                    case '*':
                            sstack.Push(ch);
                            break;
                    case ')':
                          if (!removeFromStack(pstack,sstack))
                                return false;
                            break;
                }
            }
           
            int starcount =0;
            while ( pstack.Count > 0 )
            {
              CharandStarCount temp = pstack.Pop();
                
              if (temp.startCount < sstack.Count)
               {
                  sstack.Pop(); 
              
               } 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.