Lexi's Leetcode solutions

[leetcode] Valid Parentheses | 三种括号配对

Posted on: October 1, 2013

这个没想到用stack,还傻乎乎的用一种括号配对的方法做,结果设了l1, l2, l3, r1, r2, r3六个变量,然后发现解决不了([)]这种交错的invalid问题。无奈之下看答案,原来一个stack轻松搞定。其实仔细想想,valid的前提条件是“不会出现(]这种不配的抱在一起“的情况,所以当扫到右半边时,一个stack直接比较前一个是不是自己家的左半就好了。

 

public boolean isValid(String s) {
  Stack<Character> stack = new Stack<Character>();
  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    switch (c) {
    case '(':
    case '{':
    case '[':
      stack.push(c);
      break;
    case ')':
      if (stack.isEmpty() || stack.pop() != '(')
        return false;
      break;
    case '}':
      if (stack.isEmpty() || stack.pop() != '{')
        return false;
      break;
    case ']':
      if (stack.isEmpty() || stack.pop() != '[')
        return false;
      break;
     }
   }
   return stack.isEmpty();
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: