LeetCode_Valid Parentheses

Posted on | In | Views:

Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
（判断有效的括号对）

An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example:



1. 栈匹配

括号的匹配问题是一个很直观的栈的应用问题。具体实现过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        
        stack = []
        mapping = {')': '(', ']': '[', '}': '{'}
        
        for ch in s:
            if ch in mapping:
                top = stack.pop() if stack else '#'
                if top != mapping[ch]:
                    return False
            else:
                stack.append(ch)
                
        return not stack

2. 栈匹配

后来看别人的解答过程中有一种更直观简单的栈匹配过程。具体实现过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for c in s:
            if c == '[':
                stack.append(']')
            elif c == '{':
                stack.append('}')
            elif c == '(':
                stack.append(')')
            elif not stack or c != stack.pop():
                return False
        return not stack