Fork me on GitHub

20.Vaild Parentheses

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

您的赞赏是对我最大的支持,谢谢!