leetcode 20. 有效的括号(C++)

柔情只为你懂 2023-07-15 05:57 73阅读 0赞

python版——>[leetcode 20：有效的括号(python)][leetcode 20_python]

# 题目 #

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

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

示例 1:

输入: "()"
    输出: true

示例 2:

输入: "()[]{}"
    输出: true

示例 3:

输入: "(]"
    输出: false

示例 4:

输入: "([)]"
    输出: false

示例 5:

输入: "{[]}"
    输出: true

来源：[20. 有效的括号 - 力扣（LeetCode）][20. _ - _LeetCode]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 栈配对法 #

*  定义res作为一个栈  
    遍历整个字符串，将每个左括号加入res  
    当发现右括号时，就查栈顶元素：  
    若不是其对应的左括号，直接返回false；  
    若是，该元素出栈，检查字符串中下一个元素。  
    p.s.  
    我这里判断括号是否对应用的是ASCII码的方式

<table> 
 <thead> 
  <tr> 
   <th align="center">ASCII码</th> 
   <th align="center">字符</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">40</td> 
   <td align="center">(</td> 
  </tr> 
  <tr> 
   <td align="center">41</td> 
   <td align="center">)</td> 
  </tr> 
  <tr> 
   <td align="center">63</td> 
   <td align="center">?</td> 
  </tr> 
  <tr> 
   <td align="center">91</td> 
   <td align="center">[</td> 
  </tr> 
  <tr> 
   <td align="center">93</td> 
   <td align="center">]</td> 
  </tr> 
  <tr> 
   <td align="center">123</td> 
   <td align="center">{ </td> 
  </tr> 
  <tr> 
   <td align="center">125</td> 
   <td align="center">}</td> 
  </tr> 
 </tbody> 
</table>

观察上表可知，对应括号之间的ASCII码相差1或者2  
且’?'与他们都不相近，所以可用于填充空栈

代码如下：

class Solution { 
    public:
        bool isValid(string s) { 
            vector<char> res{ '?'};
            int i = 0;
            int len = s.length();
            if(len % 2 == 1)    return false;
            while(i<len)
            {     
                char c = s[i];
                if(c == ')' || c == '}' || c == ']')
                {   
                    char cc = res.back();
                    if(cc != c - 1 && cc != c-2)
                        return false;
                    else
                        res.pop_back();
                }
                else
                    res.push_back(c);
                i += 1;
            }
            return res.back() == '?' ? true : false;
        }
    };

结果：  
![在这里插入图片描述][20200315212610150.png]

[leetcode 20_python]: https://blog.csdn.net/nanashi_F/article/details/100169366
[20. _ - _LeetCode]: https://leetcode-cn.com/problems/valid-parentheses
[20200315212610150.png]: /images/20230528/923e851efcda4b2fa29e70d46542afdb.png