給定一個隻包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字元串,判斷字元串是否有效。
有效字元串需滿足:
- 左括号必須用相同類型的右括号閉合。
- 左括号必須以正确的順序閉合。
注意空字元串可被認為是有效字元串
示例 1:
輸入: “()”
輸出: true
示例 2:
輸入: “()[]{}”
輸出: true
bool isValid(string s) {
if(s.length() == 0) return true;
stack<char> S;
for (int i = 0;i < s.length(); ++i) {
switch(s[i]) {
case ')':
{
if(!S.empty()) {
if(S.top() == '('){
S.pop();
} else {
return false;
}
}else {
return false;
}
break;
}
case ']':
{
if(!S.empty()) {
if(S.top() == '['){
S.pop();
} else {
return false;
}
}else {
return false;
}
break;
}
case '}':
{
if(!S.empty()) {
if(S.top() == '{'){
S.pop();
} else {
return false;
}
}else {
return false;
}
break;
}
case '(':
{
S.push(s[i]);
break;
}
case '[':
{
S.push(s[i]);
break;
}
case '{':
{
S.push(s[i]);
break;
}
}
}
if (S.size() != 0) {
return false;
}
return true;
}
bool isValid(string s) {
map<char,int> m{{'(',1},{'[',2},{'{',3},
{')',4},{']',5},{'}',6}};
stack<char> st;
bool res=true;
for(char c:s){
int flag=m[c];
if(flag>=1&&flag<=3) st.push(c);
else if(!st.empty()&&m[st.top()]==flag-3) st.pop();
else {res=false;break;}
}
if(!st.empty()) res=false;
return res;
}