20. Valid Parentheses

题目：

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

链接：http://leetcode.com/problems/valid-parentheses/

一刷，右半部分的else中的两次判断可以合在一句，但是容易忽略pop，不够直观。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        parenthese = {
            '(': ')',
            '[': ']',
            '{': '}'
        }
        for char in s:
            if char in parenthese:
                stack.append(char)
            else:
                if not stack:
                    return False
                prev = stack.pop()
                if parenthese[prev] != char:
                    return False
        return False if stack else True

2/9/2017, Java

最后一步一定要判断stack是空的

 1 public class Solution {
 2     public boolean isValid(String s) {
 3         Stack<Character> stk = new Stack<Character>();
 4         char a;
 5         char b;
 6         for (int i = 0; i < s.length(); i++) {
 7             a = s.charAt(i);
 8             if (a == '(' || a == '[' || a == '{') {
 9                 stk.push(a);
10             } else if (a == ')' || a == ']' || a == '}') {
11                 if (stk.empty()) return false;
12                 b = stk.pop();
13                 if (a == ')' && b == '(' || a == ']' && b == '[' || a == '}' && b == '{') ;
14                 else return false;
15             }
16         }
17         if (stk.empty()) return true;
18         return false;
19     }
20 }