速拓科技是做网站,品牌设计公司宣传画册,生成器软件,上海一家做服饰包鞋穿上用品的网站题目#xff1a;给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符串是否有效。
有效字符串需满足#xff1a;
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应…题目给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
分析由于栈先进后出的特性非常适合处理对称匹配类的问题尤其题目题目中还要求左括号必须以正确的顺序闭合。我们可以在每遇到一个左括号的时候就往栈里存放一个对应的右括号当左括号遍历完遍历到右括号时如果遍历到的右括号和栈顶的元素不匹配说明左括号没有用相同类型的右括号闭合。如果还没有遍历完右括号而栈已经空了说明有多余的右括号。如果遍历完字符串栈还没空说明有左括号没有对应的右括号如果此时栈空了说明字符串有效。
具体代码
class Solution {
public:bool isValid(string s) {stackint st;for(int i 0; i s.size(); i) {if(s[i] () {st.push());} else if(s[i] [) {st.push(]);} else if(s[i] {) {st.push(});} else if(st.empty() || s[i] ! st.top()) {return false;} else {st.pop();}}return st.empty();}
};
