我有一壶酒,足以慰平生。

0%

力扣每日一题之有效的括号

1、题目描述

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

有效字符串需满足:

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

2、示例

示例 1:

1
2
输入: "()"
输出: true

示例 2:

1
2
输入: "()[]{}"
输出: true

示例 3:

1
2
输入: "(]"
输出: false

示例 4:

1
2
输入: "([)]"
输出: false

示例 5:

1
2
输入: "{[]}"
输出: true

3.算法分析

采用栈的特性,对括号进行匹配,左括号入栈,将即将插入的元素与栈顶元素进行匹配,如果未

栈顶元素的另一半则,弹出栈顶元素,最后若栈为空则返回true,否则返回false。

  1. 初始化栈 S。

  2. 一次处理表达式的每个括号。

  3. 如果遇到开括号,我们只需将其推到栈上即可。这意味着我们将稍后处理它,让我们简单地

    转到前面的 子表达式。

  4. 如果我们遇到一个闭括号,那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左

    括号,那么我们将它从栈中弹出并继续处理。否则,这意味着表达式无效。

  5. 如果到最后我们剩下的栈中仍然有元素,那么这意味着表达式无效。

4、代码实现及测试结果

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
package com.lcx.leetCode;

import java.util.HashMap;
import java.util.Stack;

public class Demo20 {
private HashMap<Character, Character> map;

public Demo20() {
this.map = new HashMap<Character, Character>();
map.put(')', '(');
map.put('}', '{');
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();

if (topElement != this.map.get(c)) {
return false;
}
} else {
stack.push(c);
}
}
return stack.isEmpty();
}

public static void main(String[] args) {
String s = "()[]{}";
System.out.println(new Demo20().isValid(s));
}
}

运行结果
"E:\Program Files\Java\jdk1.8.0_201\bin\java.exe"

true
```

您的支持是我继续创作的动力