20. 有效的括号（栈与队列）(Leetcode刷题笔记)

欢迎大家访问我的GitHub博客

https://lunan0320.cn

题目

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

有效字符串需满足：

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

示例 1：

输入：s = “()”
输出：true

示例 2：

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

示例 3：

输入：s = “(]”
输出：false

示例 4：

输入：s = “([)]”
输出：false

示例 5：

输入：s = “{[]}”
输出：true

解题代码 C++(核心代码)

解题思路： 字符的括号匹配是栈的经典套路。 需要注意的是：此处压栈的时候对于左括号，压入的是右括号、
对于在匹配过程中栈变为空，或者不匹配的时候，说明字符串无效

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;
        for(int i = 0; i < s.size(); i++){
            //遍历字符串s
            //如果有左括号的，则压栈其对应的右括号
            if(s[i]=='(') st.push(')');
            else if (s[i]=='[') st.push(']');
            else if (s[i]=='{') st.push('}');
            //如果是右括号
            //如果在匹配的过程中，栈为空了，或者不匹配了，则无效
            else if (st.empty() || s[i]!=st.top()) return false;
            //栈不空，且左右括号匹配的时候
            else st.pop();
        }
        if(st.empty()) return true;
        else return false;
    }
};

解题代码（本地编译运行）

/* head.h */
#include <iostream>
#include <stack>
#include <string>

using namespace std;

/* myStack.h */

#include "head.h"
//字符括号匹配
class str_valid {
public:
	bool isValid(string s) {
		stack<int> st;
		for (int i = 0; i < s.size(); i++) {
			//判断是左括号的情况
			if (s[i] == '(') st.push(')');
			else if (s[i] == '[') st.push(']');
			else if (s[i] == '{') st.push('}');
			//判断是右括号的情况
			//当匹配的过程中栈为空，或者不匹配直接false
			else if (st.empty()|| s[i]!=st.top()) {
				return false;
			}
			//其他情况就是匹配了 
			else st.pop();
		}
		if (st.empty()) {
			return true;
		}
		else return false;
	}
};

/* main.cpp */

#include "myStack.h"

int main() {
	str_valid solution;
	string s = "([)]";
	cout << solution.isValid(s) << endl;
	return 0;
}

算法效率

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6.2 MB, 在所有 C++ 提交中击败了55.48%的用户