leetcode刷题：栈与队列03（有效的括号）

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;
    }
}

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

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;
    }
}

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