LeetCode 20. 有效的括号（易）

充分利用了栈先进先出的特点

题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串

示例

示例 1: 

1
2
输入: "()"
输出: true
示例 2: 
1
2
输入: "()[]{}"
输出: true
示例 3: 
1
2
输入: "(]"
输出: false
示例 4: 
1
2
输入: "([)]"
输出: false
示例 5: 
1
2
输入: "{[]}"
输出: true

考察知识点

栈、字符串

核心思想

方法一：基于栈实现

1、初始化栈 S。 2、一次处理表达式的每个括号。 3、如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处理它，让我们简单地转到前面的 子表达式。 4、如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。 5、如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。

STACK-0.png

LeetCode题解

Python版本

独立实现的基于栈的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#define Stack
class Stack:
    def __init__(self):
        """
        initialize stack
        """
        self.items = []
    
    def __str__(self):
        return str(self.items)

    def isEmpty(self):
        """
        Return Stack is empty or not
        :return: bool
        """
        return len(self.items) == 0

    def push(self, item):
        """
        Push one item into Stack
        :param item: Object
        :return: None
        """
        self.items.append(item)

    def pop(self):
        """
        Return newest item push into stack
        :return: Object
        """
        return self.items.pop()

    def peek(self):
        """
        Return newest item without stack change
        :return: Object
        """
        return self.items[-1]

    def size(self):
        """
        Return the size of stack
        """
        return len(self.items)

class Solution:
    def isValid(self, s: str) -> bool:

        if len(s) % 2 != 0:
            return False

        open_bracket = ['(', '{', '[']
        close_bracket = [')', '}', ']']
        break_pairs = {
            ")": "(",
            "}": "{",
            "]": "["
        }

        stack = Stack()
        
        for bracket in s:
            if bracket in open_bracket:
                stack.push(bracket)
            elif bracket in close_bracket and stack.size() != 0 and break_pairs[bracket] == stack.peek():
                stack.pop()
            else:
                return False

        if stack.size() == 0:
            return True
        else:
            return False

时间复杂度：\(O(n)\)，因为我们一次只遍历给定的字符串中的一个字符并在栈上进行 \(O(1)\) 的推入和弹出操作。 空间复杂度：\(O(n)\)，当我们将所有的开括号都推到栈上时以及在最糟糕的情况下，我们最终要把所有括号推到栈上。例如 ((((((((((。

有效语法糖

1、栈的声明、初始化、插入、删除，详情见“DS_栈.md”。

1
2
3
4
5
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None