题目: 有效的括号

有效的括号

难度：简单

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

1 <= s.length <= 10⁴
s 仅由括号 '()[]{}' 组成

分析

该题目因为要做匹配处理，而且符号之前可以支持嵌套，所以采用栈作为辅助结构进行解题。

循环字符串，遇到左括号则压栈，遇到右括号进行一次出栈，如果出栈的符号和当前遇到的括号是左右匹配的，则继续，直到循环字符串结束，而且栈中的数据也为空，则说明当前是有效的括号，否则是无效括号。

该算法的时间复杂度是O（n）。

题解

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

    public static boolean solute(String input){
        boolean result = true;

        Deque<Character> statck = new LinkedList<>();
        for(int i = 0; i < input.length(); i ++){
            char currentChar = input.charAt(i);
            if(currentChar == '{' || currentChar == '[' || currentChar == '('){
                statck.push(currentChar);
            }else if(currentChar == ')'){
                char lastChar = statck.pop();
                if(lastChar != '('){
                    result = false;
                }
            }else if(currentChar == ']'){
                char lastChar = statck.pop();
                if(lastChar != '['){
                    result = false;
                }
            }else if(currentChar == '}'){
                char lastChar = statck.pop();
                if(lastChar != '{'){
                    result = false;
                }
            }
        }

        if(!statck.isEmpty()){
            result = false;
        }

        return result;
    }

}