题目描述
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
代码 C++
- 思路一、一看到题目，完全没思路，突然想到栈，但是如何用，还真不知道，后来清明出去玩了两天，再回来看到这道题，有思路了，写了半个小时，好弱啊。下面是正题。。
碰到 '(' '{' '[' 直接进栈，碰到 ')' '}' ']' 和前一字符进行比较。具体看代码吧。（源码面前，了无秘密）
class Solution {
public:
bool isValid(string s) {
if(s == ""){
return true;
}
// 配对的肯定是偶数，奇数直接返回 false
if(s.size()%2 != 0){
return false;
}
// 用栈来存放数据
stack<char> sk;
sk.push(s[0]); // 先把第一个存放
int i=1;
while(i < s.size()){
// 如果后一个字符和栈顶元素配对，则栈顶元素出栈
if(fab(sk.top(), s[i]) == true){
sk.pop(); // 栈顶元素出栈
if(i == s.size()-1){ // 到达最后一个字符，则完成操作，配对完成
break;
}
// 配对之后，现在 i+1 位是 '{' '(' '[' 则进栈
if(s[i+1] == '{' || s[i+1] == '[' || s[i+1] == '('){
sk.push(s[i+1]);
i = i + 2;
}
else{ // 配对之后，现在 i+1 位是 '}' ')' ']' 则不能进栈，继续和栈顶元素进行比较
i = i + 1;
}
}
else{ // 如果后一个字符和栈顶元素不配对，则进栈
sk.push(s[i]);
i = i + 1;
}
}
// 如果最终栈为空，则配对；栈不为空，则不配对
return sk.empty();
}
bool fab(char a, char b){
if(a == '(' && b == ')'){
return true;
}
if(a == '{' && b == '}'){
return true;
}
if(a == '[' && b == ']'){
return true;
}
return false;
}
};
- 思路二、看讨论区写的。思路和思路一基本一致，但是效率，代码风格比思路一清晰多了。推荐。
class Solution {
public:
bool isValid(string s) {
if(s == ""){
return true;
}
// 配对的肯定是偶数，奇数直接返回 false
if(s.size()%2 != 0){
return false;
}
// 用栈来存放数据
stack<char> sk;
for(int i=0; i < s.size(); i++){
switch(s[i]){
case '{':
sk.push(s[i]);
break;
case '(':
sk.push(s[i]);
break;
case '[':
sk.push(s[i]);
break;
case '}':
if(sk.empty() || sk.top() != '{'){
return false;
}
sk.pop();
break;
case ')':
if(sk.empty() || sk.top() != '('){
return false;
}
sk.pop();
break;
case ']':
if(sk.empty() || sk.top() != '['){
return false;
}
sk.pop();
break;
}
}
// 如果栈为空则配对成功。主要是防止有 "((" 情况的发生
return sk.empty();
}
};
