转载

20.Vaild Parentheses

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

有效字符串需满足：

1.左括号必须用相同类型的右括号闭合。

2.左括号必须以正确的顺序闭合。

3.注意空字符串可被认为是有效字符串。

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

代码如下:

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为空，就可以得出该字符串是无效的括号

原文 https://thorns.cn/2020/01/09/leetcode_20.html

正文到此结束