【字符串/栈】有效的括号（leetcode20）

桃扇骨 2022-10-19 00:48 250阅读 0赞

## 一、题目 ##

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    
    有效字符串需满足：
    
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]

## 二、分析 ##

有效的括号应该满足：每一个左括号，在恰当的位置都会有一个右括号与之对应。

简单来讲，本题可看作是一个**消消乐游戏**，从左向右遍历字符串，当左括号找到恰当位置的右括号时，就将这对括号**消掉**。当遍历结束时，所有的括号对都消除了，那么字符串s满足要求，返回true；否则，返回false。

由于是按照从左向右固定的顺序遍历，所以先出现的左括号一定是后消掉的。因此，自然联想到使用栈的性质——先进后出，来解决此题。

对于本题，具体步骤如下：

*  从左向右依次遍历字符串的每一个字符
 *  如果字符是左括号，则存入栈中；如果是右括号，则做进一步判断
 *  如果是右括号，先判断此时栈是否为空。如果是空的，则右括号无法小消除，返回false；如果栈不是空的，再将此字符于栈顶元素进行比较，判断是否符合条件。
 *  当遍历完所有字符元素，判断栈是否为空。如果是空，说明所有括号都消掉了，返回true；否则，返回fasle。

## 三、题解 ##

根据以上的分析，C++实现如下：

class Solution { 
    public:
        stack<char> stk;
        unordered_map<char, char> pairs = {  { '(', ')'}, { '[', ']'}, { '{', '}'} };
       
        bool isValid(string s) { 
            for(int i=0; i<s.size(); ++i)
            { 
                if(s[i]=='(' || s[i]=='{' || s[i]=='['){ 
                    stk.push(s[i]); //如果是左括号，则存入栈中
                }
                else{   //如果是右括号，则和栈顶元素进行比较
                    if(!stk.empty() && s[i]==pairs[stk.top()]){  
                        stk.pop();
                    }
                    else{ 
                        return false;
                    }
                }
            }
            if(stk.empty())
                return true;
            else
                return false;
        }
    };

提交结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]: /images/20221005/8251bfdd0242410d917de778335ce03c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]: /images/20221005/7b20427be7a24950836f5a337a3885bc.png