20. 有效的括号

力扣题目链接

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

有效字符串需满足：

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

示例 1:

• 输入: “()”
• 输出: true

示例 2:

• 输入: “()[]{}”
• 输出: true

示例 3:

• 输入: “(]”
• 输出: false

示例 4:

• 输入: “([)]”
• 输出: false

示例 5:

• 输入: “{[]}”
• 输出: true

显然用栈思想

package com.programmercarl.stacks_queues;

import java.util.Stack;

/**
 * @ClassName IsValid
 * @Descriotion TODO
 * @Author nitaotao
 * @Date 2022/6/29 13:41
 * @Version 1.0
 **/
public class IsValid {
    public boolean isValid(String s) {
        /**
         * 显然这题用栈做
         */
        Stack stack = new Stack();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            //左符号加入栈中
            if (chars[i] == '(' || chars[i] == '[' || chars[i] == '{') {
                stack.push(chars[i]);
            } else {
                //如果直接是右括号开头，返回false
                if (stack.size() == 0) {
                    return false;
                }
                char item = (char) stack.pop();
                switch (item) {
                    case '(':
                        if (chars[i] != ')') {
                            return false;
                        }
                        break;
                    case '[':
                        if (chars[i] != ']') {
                            return false;
                        }
                        break;
                    case '{':
                        if (chars[i] != '}') {
                            return false;
                        }
                        break;
                }
            }
        }
        return stack.size() == 0;
    }
}

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

发现这题之前做过，看看当时思想。

class Solution {
   public boolean isValid(String s) {
        String[] arr = s.split("");
        if (arr.length % 2 != 0) {
            //如果不是偶数，必有一个不匹配
            return false;
        }
        // ( [ {  为进   ) ] }为出
        LinkedList queue = new LinkedList(); //栈结构
//        for (int i = 0; i < arr.length; i++) {
//            System.out.print(arr[i]);
//        }
//        System.out.println();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].equals("{") || arr[i].equals("[") || arr[i].equals("(")) {
                queue.addFirst(arr[i]);
            } else {
                //如果先进来的是右括号
                if (queue.size() == 0) {
                    return false;
                }
                String left = (String) queue.remove();


                if (left.equals("{")) {
                    if (arr[i].equals("}")) {
                        continue;
                    } else {
                        return false;
                    }
                } else if (left.equals("[")) {
                    if (arr[i].equals("]")) {
                        continue;
                    } else {
                        return false;
                    }
                } else if (left.equals("(")) {
                    if (arr[i].equals(")")) {
                        continue;
                    } else {
                        return false;
                    }
                }
            }
        }
        if (queue.size() != 0) {
            return false;
        }
        return true;
    }
}
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

hhhhhh，当时暴力思想，还是太年轻哦。