『牛客|每日一题』有效括号序列

作者简介：一位喜欢写作，计科专业大二菜鸟

个人主页：starry陆离

首发日期：2022年7月17日星期日

上期文章：『牛客|每日一题』 栈的压入、弹出序列_

订阅专栏：『牛客刷题集锦』

每日推荐：基础算法无论在研究生面试还是求职面试都是十分重要的一环，这里推荐一款算法面试神器：牛客网-面试神器；算法题只有多刷勤刷才能保持思路与手感，大家赶紧行动起来吧（温馨提示：常见的面试问答题库也很nice哦）

如果文章有帮到你的话记得点赞+收藏支持一下哦

1.每日一题

2.方法1：左括号入栈

2.1思路分析

遍历字符串，遇到'(','{','['这三种字符的时候，将字符入栈stk；而遇到')','}',']'这三种字符的时候则让对应的匹配字符出栈。具体规则如下：

• step 1：引入辅助栈stk，遍历字符串，每次遇到'(','{','['字符的时候将字符入栈stk
• step 2：当遇到')','}',']'字符的时候，则检查栈是否空，且顶元素是否为匹配元素（如{和}匹配等），如果栈空或者栈顶元素不为匹配元素则括号序列不合法
• step 3：当栈非空，且栈顶元素为匹配元素，则栈顶元素出栈。
• step 4：循环匹配字符串，直到每次字符处理完
• step 5：检查栈stk是否为空，栈为空则序列合法，否则不合法（当括号以正确顺序关闭时则最后的栈为空）

2.2核心代码

import java.util.*;
public class Solution {
    
    /** * @param s string字符串 * @return bool布尔型 */
    public boolean isValid (String s) {
    
        // write code here
        Stack<Character>stk=new Stack<Character>();
        int l=s.length();
        for(int i=0;i<l;++i){
    
            char a=s.charAt(i);
            if(a=='('||a=='['||a=='{')stk.push(a);
            if(a==')'){
    
                if(stk.isEmpty()||stk.peek()!='(') return false;
                stk.pop();
                continue;
            }
            if(a==']'){
    
                if(stk.isEmpty()||stk.peek()!='[')return false;
                stk.pop();
                continue;
            }
            if(a=='}'){
    
                if(stk.isEmpty()||stk.peek()!='{')return false;
                stk.pop();
                continue;
            }
        }
        return stk.isEmpty()?true:false;
    }
}

3.方法2：右括号入栈

3.1思路分析

仍然是遍历字符串，借助辅助栈

• step 1：当遇到'(','[','{'这三种字符的时候则让对应的匹配字符入栈(分别对应')',']','}')
• step 2：当出现的字符不是'(','[','{'这三种字符时，则先判断栈是否为空或者当前字符是否与栈顶元素一样，
• step 3：当栈空或者当前字符与栈顶字符不一样时，则括号序列不合法，直接返回；
• step 4：否则栈顶元素出栈。遍历字符串直到所有元素遍历完成。最后判断栈是否为空，不为空则括号序列不合法；否则为合法序列。

3.2核心代码

import java.util.Stack;

public class Solution {
    
    public boolean isValid(String s) {
    
		Stack<Character> stack = new Stack<Character>();
		//使用foreach循环
		for (char c : s.toCharArray()) {
    
			if (c == '(')
				stack.push(')');
			else if (c == '{')
				stack.push('}');
			else if (c == '[')
				stack.push(']');
			else if (stack.isEmpty() || stack.pop() != c)
				return false;
		}
		return stack.isEmpty();
	}
}

订阅专栏：『牛客刷题集锦』

每日推荐：基础算法无论在研究生面试还是求职面试都是十分重要的一环，这里推荐一款算法面试神器：牛客网-面试神器；算法题只有多刷勤刷才能保持思路与手感，大家赶紧行动起来吧（温馨提示：常见的面试问答题库也很nice哦）

如果文章有帮到你的话记得点赞+收藏支持一下哦