526互联

20. 有效的括号

发布时间 2023-10-25 11:51:00作者: DawnTraveler

1.题目介绍

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：
输入：s = "()"
输出：true

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

示例 3：
输入：s = "(]"
输出：false

提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

2.题解（栈的使用）

利用栈先进后出（FILO）的特点，通过入栈，出栈的操作很好的实现括号的匹配

2.1 初解

//
// Created by trmbh on 2023-10-25.
// 20. 有效的括号
//
#include <iostream>
#include <string>
#include <stack>
class Solution {
public:
    bool compare(char c1, char c2){
        if (c1 == '(' && c2 == ')') return true;
        if (c1 == '{' && c2 == '}') return true;
        if (c1 == '[' && c2 == ']') return true;
        return false;
    }
    bool isValid(std::string s) {
        std::stack<char> st;
        for (char c:s){
            if(c == '(' || c == '{' || c == '[')
                st.push(c);
            else if (st.empty()) return false;
            else if (compare(st.top(),c)) st.pop();
            else return false;
        }
        if (st.empty()) return true;
        else return false;
    }
};

int main(){
    Solution solution;
    std::string str = "()[]{}";
    bool res = solution.isValid(str);
    if (res) std::cout<<"匹配成功";
    else std::cout<<"匹配失败";
}

2.2 优化

1. 括号匹配字符串必是偶数个字符

2. 利用键值对映射进行匹配

3. 结尾处直接return stk.empty();即可，不需要使用if判断

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0 || s.empty()) return false;
        stack<char> stk;
        unordered_map<char,char> pairs ={
            {')','('},
            {']','['},
            {'}','{'}
        };
        for (char ch:s){
            if(pairs.count(ch)){
                if (stk.empty() || stk.top() != pairs[ch])
                    return false; 
                stk.pop();
            }
            else{
                stk.push(ch);
            } 
        }
        return stk.empty();
    }
};