题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
看到这道题目，我们自然想到使用栈来解决这个问题。大致思路如下：
- 首先建立一个哈希表，构建好括号之间的对应关系
- 遍历字符串之前先判断字符个数，如果为奇数则不可能配对，返回false
- 遍历字符串
- 首先通过判断字符是否是哈希表的key来判断是否为右括号
- 如果为右括号，栈非空并且栈顶有对应括号配对，则出栈，否则返回false
- 如果为左括号则进栈
- 最后通过判断栈是否为空来判断true or false
class Solution {
public:
bool isValid(string s) {
map<char, char> map;
map[')'] = '(';
map[']'] = '[';
map['}'] = '{';
stack<char>st;
while(s.length()%2==0){
for(char c:s){
if(map.count(c)>0){
if(!st.empty() && map[c]==st.top())
st.pop();
else
return false;
}
else
st.push(c);
}
if(st.empty())
return true;
return false;
}
return false;
}
};
