Queue solution doesn't pass the test, can anybody tell me why?thanks


  • 0
    Y
    public class Solution {
        public boolean isValid(String s) {
            Queue q=new LinkedList<Character>();
            int l=s.length();
            for(int i=0;i<l;i++){
                char c=s.charAt(i);
                if(q.peek()==null){
                    q.offer(c);
                }else{
                    char ch=(char)q.peek();
                    if(ch=='('&&c==')'||ch=='{'&&c=='}'||ch=='['&&c==']'){
                        q.poll();
                    }else{
                        q.offer(c);
                    }
                }
            }
            if(q.size()==0){return true;}
            return false;
        }
    }
    

    this is my code and i think it should pass test, but it doesn't pass some test like
    "( [ ) ] ",i don't know why,please help me


  • 1

    @yuntianfs First I have no idea why you would choose to adopt queue here, isn't that obvious enough to select stack? Second, you are not checking the coming parentheses with the top one inside queue, so that test case you provided here would definitely pass.

    Here is a typical solution using stack in C++, quite similar logic.

    class Solution {
    public:
        bool isValid(string s) 
        {
            stack<char> parentheses;
            for(int i = 0; s[i]; ++i)
            {
                if(s[i]=='(' || s[i]=='[' || s[i]=='{') parentheses.push(s[i]);
                else
                {
                    switch(s[i])
                    {
                        case ')': if(!parentheses.empty() && parentheses.top()=='(') { parentheses.pop(); break; } else return false;
                        case ']': if(!parentheses.empty() && parentheses.top()=='[') { parentheses.pop(); break; } else return false;
                        case '}': if(!parentheses.empty() && parentheses.top()=='{') { parentheses.pop(); break; } else return false;
                        default: break;
                    }
                }
            }
            return parentheses.empty();
        }
    };
    

  • 0
    Y

    @LHearen thanks very much.
    I think i confused queue and stack...


Log in to reply
 

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