LeetCode 20 — Valid Parentheses
题目描述
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
这道题的主要要求就是括号的匹配,那么我们很自然的想到我们可以借助栈来解决这道问题,对于这道题的解释也很简单,首先就是基本的括号匹配,如果是字符串为空的话,也判断为匹配成功,因此,我们可以写出一下代码:
class Solution {
public:
bool isValid(string s)
{
if(s.size() == 0){
return true;
}
stack<char> st;
st.push(s[0]);
for(int i = 1; i < s.size(); i++)
{
if( !st.empty() && isMatch(st.top(), s[i]))
{
st.pop();
}
else
{
st.push(s[i]);
}
}
if(st.empty())
{
return true;
}else
{
return false;
}
}
bool isMatch(char s, char p)
{
if((s == '(' && p == ')')|| (s == '{' && p == '}')|| (s == '[' && p == ']'))
return true;
else
return false;
}
};
这就是一种常规的解法,使用栈,并且将匹配成功的出栈,最后检查栈里面是否还有剩余,就是一个很好的解决办法,之后在网上看别人的答案的是偶,发现了另外一种想法,感觉也挺不错的,所有就po出来:
bool isValid(string s)
{
if(s.length() == 0){
return true;
}
stack<char> st;
st.push(s[0]);
for(int i = 1; i < (int)s.length(); i++)
{
char c = s[i];
char ret = getPaif(c);
if(ret == 0)
{
st.push(c);
}else{
if(st.empty() || st.top() != ret){
return false;
}
st.pop();
}
}
return st.empty();
}
char getPair(char c) {
char ret = 0;
switch (c) {
case ')':
ret = '(';
break;
case '}':
ret = '{';
break;
case ']':
ret = '[';
break;
default:
break;
}
return ret;
}
这种方法不是直接匹配,而是通过一个函数,找到我想要的那个符号,如果接下的符号和我想要的不是一个的话,我就直接返回false,也是一个不错的想法。