有效的字符串

发表于 更新于 分类于 本文字数： 301 阅读时长 ≈ 3 分钟

题目描述

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

有效字符串需满足：

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

⚠️注意空字符串可被认为是有效字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true

解题思路

循环遍历字符串，使用栈 Stack 保存未匹配的左侧字符串，包括 (、{、[，
如果遇到对应的右侧字符串， 则选择出栈 pop，直到循环完成，最后判断栈是否为空。

  1. 栈为空，则说明该字符串是有效字符串
  2. 栈为空，则说明该字符串是无效字符串

代码

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
public class ValidStr {
    public static void main(String[] args) {

        // 假设这是输入的字符串
        String str = "{[(]}";

        Stack<String> stack = new Stack<>();
        Map<String, String> map = new HashMap<>();
        map.put(")", "(");
        map.put("}", "{");
        map.put("]", "[");

        for (int i = 0; i < str.length(); i++) {
            String s = String.valueOf(str.charAt(i));
            if (map.containsKey(s) && !stack.isEmpty()) {
                String peek = stack.peek();
                if (peek.equals(map.get(s))) {
                    stack.pop();
                    continue;
                }
            }
            stack.push(s);
        }

        // 判断stack是否为空
        System.out.println(stack.isEmpty());
    }
}

项目地址