20.Vaild Parentheses

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

有效字符串需满足:

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

解题思路:可以用stack的先进后出的特性和map来解决此题,使用map存放所有(),[],{},需要注意的是将反向的括号作为键,正向的作为值,遍历字符串,判断字符是否正向,如果是正向的就放入到stack中,如果不是判断栈里面的元素是否等于当前遍历的字符,不等于说明该字符串就是无效的。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution{
  bool isValid(string s)
  {
   map<char,char> p = {{')','('},{']','['},{'}','{'}};
    stack<char> st;
    for (auto ch : s)
    {
      //判断当前字符是否是正向的,如果是,放入到stack中
      if (!p.count(ch))
      {
        st.puch(ch);
      }
      else
      {
        if (st.empty() || p[ch] != st.top())
        {
          return false;
        }
        else
        {
          //说明是一对有效的符号,弹出接着遍历下一对
          st.pop();
        }
      }
    }
    return st.empty();
  }
};

可能刚开始看着的时候不太理解,如果换作java的stack就好理解,因为java中的stack pop函数会返回对象,而C++的不会,所以这里借助了map实现,Java可以判断遍历的字符是正向的括号,如果是就放入对应的反向括号到Stack中,如果遍历遇到反向的括号就弹出Stack最后一位元素,跟当前字符比较,不相等或者Stack为空,就可以得出该字符串是无效的括号

留下评论