上班摸鱼打代码@o@
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()" 输出：true 示例 2：
输入：s = "()[]{}" 输出：true 示例 3：
输入：s = "(]" 输出：false 示例 4：
输入：s = "([)]" 输出：false 示例 5：
输入：s = "{[]}" 输出：true
提示：
1 <= s.length <= 104 s 仅由括号 '()[]{}' 组成
AC代码
代码语言：javascript复制class Solution {
public:
bool isValid(string s) {
stack<char>temp;
for(auto & it:s)if(it=='('||it=='['||it=='{')temp.push(it);
else if(temp.empty()||it==')'&&temp.top()!='('||it==']'&&temp.top()!='['||it=='}'&&temp.top()!='{')return false;
else temp.pop();
return temp.empty();
}
};思路分析
成双成对……
首先得看懂题目，到底哪些是满足要求的字符串，我举一些例子：
最明显的：() [] {}
嵌套的：{[()]}
但是这样也可以：{ () ([]) [] {} }
这种部分式对称，我们可以用栈来解决。
我们按照处理一对弹出一对的方式，遍历字符串，遇到（ 就压栈，遇到 ），如果式满足要求的那么它前一个一定是 （ ，因为我们用栈是处理一对弹出一对，不会出现嵌套的一对，但是栈中可以出现{ [ ( 这样的。遍历完毕之后判断栈是不是空的，如果是空的，说明都是一对一对的，因为只有是一对才会弹栈，如果最后栈不是空的，说明有一只单身狗，或者是很多只单身狗。
代码中可以看到else if的条件判断中也判断了栈是否为空，因为有一种情况是第一个字符串就是右括号，那么就不会压栈，如果在栈为空的情况下弹栈会出错，而且第一个字符就是右括号的话，那就直接把它给寄了return回去。
