题目
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
思路
典型的栈问题,数据结构书中都有用栈来作括号匹配的问题。
①字符串长度为奇数,直接返回false
②“( ] )”,当有这样的右括号时,也让他入栈,最后判断栈非空,则返回 false;
③“( ) { } } {”,
④“{ [ ] }”,
代码
class Solution {
public:
bool isValid(string s) {
int len = s.length();
bool flag;
if (len % 2 != 0)
flag = false;
stack<char> st;
int i;
for (i = 0; i < len; i++) {
// 遇到左括号,入栈
if (s[i] == 40 || s[i] == 91 || s[i] == 123) {
st.push(s[i]);
}
// 遇到右括号,取栈顶元素,看是否匹配。匹配则出栈,不匹配则入栈
char a;
if (s[i] == 41 || s[i] == 93 || s[i] == 125) {
// 遇到右括号时,栈中无元素,则直接返回false
if (st.empty()) {
flag = false;
break;
}
if (!st.empty()) {
a = st.top();
}
if ((a == 40 && s[i] == 41) || (a == 91 && s[i] == 93) || (a == 123 && s[i] == 125)) {
st.pop(); // 匹配则出栈
}else{
st.push(s[i]); // 不匹配则入栈
}
}
}
if (i != len) {
return flag;
}
if (i == len && st.empty())
flag = true;
return flag;
}
};
答案思路:
建立map,键为右括号,值为左括号。
unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};