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

Posted by: lexigrey on: October 1, 2013

• In: leetcode
• 1 Comment

这个没想到用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();
}

Tags: stack/queue