用栈解决括号配对问题。

20.题目链接-来源：力扣（LeetCode）

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”
输出：true

思路：

括号的配对，可以用栈来解决。因为对于一个有效的括号字符串，当第一个反括号出现时，一定可以与栈顶的正括号配对，消去栈顶元素。这样不停地用反括号消去栈顶元素，当最后一个字符访问后，栈一定为空。
于是我们只要模拟这样的栈特性，当反括号出现时，就比较栈顶元素是否与其配对，若配对则消去。当遍历字符串结束后，以栈是否为空来作为判断字符串是否有效的依据。
时间复杂度：O(n)
空间复杂度：O(n)

实现：

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
class Solution {
    public boolean isValid(String s) {
        Stack<Character> pot = new Stack<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (pot.isEmpty() || !pot.peek().equals(getCounterPart(c))) {
                pot.push(c);
            } else {
                pot.pop();
            }
        }
        return pot.isEmpty();
        
    }
    
    private char getCounterPart(char c) {
        if (c == ')') {
            return '(';
        } else if( c == ']') {
            return '[';
        } else if (c == '}') {
            return '{';
        } else {
            return '\0';
        }
    }
}