从零开始算法之路 ---- 有效的括号

淩亂°似流年 2021-11-10 04:22 326阅读 0赞

**前言**:小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）  
**题源:** 力扣(LeetCode）[https://leetcode-cn.com/problems/valid-parentheses][https_leetcode-cn.com_problems_valid-parentheses]  
**题目描述:**  
  给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

1.左括号必须用相同类型的右括号闭合。  
  2.左括号必须以正确的顺序闭合。  
**注意**:空字符串可被认为是有效字符串。

**示例 1:**

输入: “()”  
输出: true  
示例 2:

输入: “()\[\]\{\}”  
输出: true  
**思路:顺序栈（用一位数组实现）** 1.我用的是暴力解题的笨办法，我把这个题理解为括号匹配问题，帮每一个左括号找到正确匹配的右括号，如果所有左括号都有相应的正确的右括号匹配返回 true,否则返回 false。我的笨办法就是先把普遍的的情况考虑进去，然后在把特殊情况考虑进去，暴力破解完成。  
   2.**两种普遍情况**（1）可以观察到，如果从左到右扫描一个字符串，那么每一个右括号将与最近遇到那个未匹配左括号相匹配。然后可以联想到从左到右扫描过程中把所遇到的左括号放到栈中。每当在后续的扫描过程中遇到一个右括号时，就将它与栈顶的左括号( 如果存在) 相匹配，同时在栈顶删除该左括号。（2）如果括号的个数为奇数则肯定不会匹配，返回 false;  
**特殊情况:**(3) 右括号开始则肯定不完全匹配，如：s = " \])\}()\{\}\[\] "。**解题具体思路看代码。**

###### 代码： ######

class Solution { 
    public:
      // 暴力解决
        bool isValid(string s) { 
            // 特殊情况 s = "][]" 字符串从左括号开始
            if(s[0] == ')' || s[0] == ']' || s[0] == '}') return false; 
            // 奇数个数括号肯定不完全匹配
            else if(s.length() % 2 != 0) return false;
            stack<char> str;
            for(int i = 0; i < s.length(); i++){ 
                // 遇到左括号，进栈 
                if(s[i] == '(' || s[i] == '[' || s[i] == '{' ) str.push(s[i]);
                // 遇到右括号 stack.top() 获取栈顶元素并不删除 
                // 如果相等(匹配)，出栈 删除 
                else if(s[i] == ')' && str.top() == '(') str.pop(); 
                else if(s[i] == ']' && str.top() == '[') str.pop(); 
                else if(s[i] == '}' && str.top() == '{') str.pop(); 
                // 这几种情况考虑在内，之外的情况就肯定不匹配（特殊情况）
                // 对应情况：s = "(()])}[}[}[]][}}[}{})][[(]({])])}}(])){)((){";
                // 执行到 s[3]时 s[3]==']' str.top() =='(',到这里就可以结束了，这里不匹配，
                //后面都匹配也没用
                else return false;
             }
             return str.empty();        
        }
    };

[https_leetcode-cn.com_problems_valid-parentheses]: https://leetcode-cn.com/problems/valid-parentheses