[Leetcode]有效的加号
Leetcode-有效的加号
题目描述
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1: 输入: “()” 输出: true
示例 2: 输入: “()[]{}” 输出: true
示例 3: 输入: “(]” 输出: false
示例 4: 输入: “([)]” 输出: false
示例 5: 输入: “{[]}” 输出: true
解题思路
借助栈的先进后出，当遇到左括号则进栈，遇到右括号则判断是否与栈顶配对，如果配对则出栈，不配对可提前返回flase。
实现代码
class Solution {
public:
bool isValid(string s) {
int len=s.length();
if(len==0)
return true;
if(len%2==1) //如果为奇数一定不是有效的
return false;
map<char,char> character={
{')','('},
{']','['},
{'}','{'}
};
stack<char>sta;
for(char ch:s){
if(ch=='('||ch=='['||ch=='{') //左括号进栈
sta.push(ch);
else{ //右括号
if(!sta.empty()&&character[ch]==sta.top()) //判断是否与栈顶配对
sta.pop();
else
return false;
}
}
if(sta.empty()) //字符串遍历完栈为空则说明有效
return true;
else //否则说明无效
return false;
}
};
