括号序列

题目描述

给出一个仅包含字符’(‘,’)’,’{‘,’}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，”()”和”()[]{}”都是合法的括号序列，但”(]”和”([)]”不合法。

示例1

输入

复制

"["

返回值

复制

false

示例2

输入

复制

"[]"

返回值

复制

true

栈

• 如果栈为空，那么入栈
• 如果栈不为空，并且当前的字符与栈顶元素匹配，那么出栈
• 如果栈不为空，并且当前的字符与栈顶元素不匹配，那么入栈
• 如果遍历结束，栈中的元素不为空，说明是false，否则是true

import java.util.*;
public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        
        Deque<Character> stack = new LinkedList<>();
        int n = s.length();
        
        char [] arr = s.toCharArray();
        for(int i=0;i<n;i++){
            char c = arr[i];
            
            if(!stack.isEmpty()){
                if((c==']'&&stack.peek()=='[')
                   ||(c == ')'&&stack.peek()=='(')
                   ||(c == '}'&&stack.peek()=='{')){
                    stack.pop();
                }else{
                    stack.push(c);
                }
            }else{
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

赏

谢谢你请我吃糖果

微信