【Leetcode】20.有效的括号

20 有效的括号

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

有效字符串需满足：

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

示例 1:
输入: “()”
输出: true

示例 2:
输入: “()[]{}”
输出: true

示例 3:
输入: “(]”
输出: false

示例 4:
输入: “([)]”
输出: false

示例 5:
输入: “{[]}”
输出: true

思路：
核心思路是用栈来解决问题，哈希表用来简化问题。遍历整个字符串的每一个字符，如果是左括号则入栈；如果是右括号，则判断栈顶是否是它所对应的左括号，如果不是直接返回true，如果是则将栈顶的左括号弹出。这样一来，遍历完整个字符串后，如果栈中还有元素，则说明没有完全匹配，返回false。如果遍历完栈空了，则返回true。
哈希表是用来将右括号（key）和左括号（value）对应起来。

代码：

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
class Solution {
    private HashMap<Character, Character> map;
    //构造器中初始化mappings
    public Solution(){
        //将哈希表map中放入三个键值对
        this.map = new HashMap<Character, Character>();
        this.map.put(')', '(');
        this.map.put('}', '{');
        this.map.put(']', '[');
    }
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            //如果目前的字符是一个右括号
            if(this.map.containsKey(c)){
                //获得栈顶元素，如果栈顶是空，则记为#
                char topElement = stack.empty() ? '#' : stack.pop();
                //若栈顶不等于对应的左括号，直接返回false
                if (topElement != this.map.get(c))
                    return false;
                //否则栈顶等于对应的左括号，则什么都不用做，上面已经把栈顶pop了
            }
            else{
                //如果目前字符是一个左括号，就把它压进栈
                stack.push(c);
            }
        }
        //如果经过上述遍历，栈中仍有元素，则返回false。
        return stack.isEmpty();
    }
}

2020.8.14二刷更新

方法

我们先分析有效括号的定义：

  • 首先，对于每一个出现过的左括号，之后都需要出现一个相对应的右括号。
  • 其次，“括号必须以正确的顺序括回”。这句话可以理解为：在当前遍历到的左括号仍然完全全部匹配时，第一个出现的左括号，必须要与最后一个出现的右括号对应，最后一个出现的左括号，必须要与第一个出现的右括号对应。（如示例5）

这样的先入后出的顺序自然让我们想到了栈结构。因此我们可以借助一个栈来实现算法。算法流程如下：

  • 准备一个栈，之后依次遍历字符串的每一个字符
  • 如果遍历到左括号，则将一个相应的右括号加入到栈中。
  • 如果遍历到右括号，则检查这个右括号和栈顶的右括号类型是否相等，如果不相等或栈中不存在可以比较的括号了，则不匹配直接返回false。如果相等则弹出这个栈中元素，继续向下遍历。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for(int i = 0; i < s.length(); i++){
        //遍历到左括号的情况
        if(s.charAt(i) == '(')
            stack.push(')');
        else if(s.charAt(i) == '[')
            stack.push(']');
        else if(s.charAt(i) == '{')
            stack.push('}');
        //遍历到右括号的情况
        else{
            if(stack.isEmpty() || s.charAt(i) != stack.peek())
                return false;
            else
                stack.pop();
        }
    }
    return stack.isEmpty();
}

2021.1.3三刷更新

从头到尾遍历字符串

  • 如果当前字符为左括号，则将这个左括号入栈
  • 如果当前字符是右括号，则比较当前栈顶的左括号是否和它对应，如果对应则匹配，可以将这个左括号出栈了。如果不匹配或者栈已空（没有左括号来和这个右括号匹配了），则返回false。
  • 遍历完字符串后，如果栈中还有尚未匹配的左括号，则返回false。否则返回true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isValid(String s) {
    if(s == null || s.length() == 0)
        return true;
    Map<Character, Character> map = new HashMap<>();
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');
    Stack<Character> stack = new Stack<>();
    for(int i = 0; i < s.length(); i++){
        if(s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}'){
            if(stack.isEmpty() || map.get(stack.peek()) != s.charAt(i))
                return false;
            stack.pop();
        }
        else
            stack.push(s.charAt(i));
    }
    return stack.isEmpty();
}