[leetcode] Valid Parentheses | 三种括号配对
Posted October 1, 2013
on:这个没想到用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
1 | [Leetcode] 20. Valid Parentheses – codefighterblog
February 28, 2016 at 10:04 pm
[…] https://leetcodenotes.wordpress.com/2013/10/01/leetcode-valid-parentheses-%E4%B8%89%E7%A7%8D%E6%8B%A… […]