题目描述
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
输入和输出
输入：s = “()”
输出：true
输入：s = “()[]{}”
输出：true
输入：s = “([)]”
输出：false
提示
- 1 <= s.length <= 10e4
- s 仅由括号 ‘()[]{}’ 组成
思路1
利用栈的思想，之后判断每个括号是否满足条件。
AC代码（C++）
class Solution {
public:
bool isValid(string s) {
stack<char> st;
int n = s.size();
for (int i = 0; i < n; ++i) {
if (st.empty() || s[i] == '(' || s[i] == '{' || s[i] == '[') {
st.push(s[i]);
} else if (s[i] == ')') {
if (st.top() == '(') {
st.pop();
} else {
st.push(s[i]);
}
} else if (s[i] == '}') {
if (st.top() == '{') {
st.pop();
} else {
st.push(s[i]);
}
} else if (s[i] == ']') {
if (st.top() == '[') {
st.pop();
} else {
st.push(s[i]);
}
}
}
if (st.empty()) {
return true;
} else {
return false;
}
}
};
思路2
还是利用栈的思想，但是在思路1之上做了优化，遇到左扩号直接加入与之对应的右括号，之后判断右括号是否与栈顶元素相同，如果相同就删除，如果不相同就直接返回false。
AC代码（Java）
class Solution {
public boolean isValid(String s) {
Stack<Character> st = new Stack<>();
for (char ch : s.toCharArray()) {
if (ch == '(') {
st.push(')');
} else if(ch == '{') {
st.push('}');
} else if(ch == '[') {
st.push(']');
//Java中pop既删除，又返回顶元素的值。
} else if (st.isEmpty() || ch != st.pop()) {
return false;
}
}
return st.isEmpty();
}
}
思路3
直接用循环替换满足的一对括号，之后判断被替换的字符串是否为空字符串，如果是则是有效的括号，反之，则不是。
AC代码（Python）
class Solution:
def isValid(self, s: str) -> bool:
while '()' in s or '{}' in s or '[]' in s:
s = s.replace('()', '');
s = s.replace('{}', '');
s = s.replace('[]', '');
return len(s) == 0;
