首页 > itarticle > leetcode_valid parentheses

leetcode_valid parentheses

admin 11月 13, 2020 0

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 :
    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 :
    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
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能