首页 > 代码库 > 20. Valid Parentheses(C++)

20. Valid Parentheses(C++)

Given a string containing just the characters ‘(‘‘)‘‘{‘‘}‘‘[‘ and ‘]‘, determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Solution :
 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         if(s.size()<2) return false;
 5         stack<char> stk;
 6         for(int i=0;i<s.size();i++){
 7             if((s[i]==()||(s[i]==[)||(s[i]=={)) stk.push(s[i]);
 8             if((s[i]==})||(s[i]==])||(s[i]==))){
 9                 if(stk.empty()) return false;
10                 char c=stk.top();
11                 stk.pop();
12                 switch (s[i]){
13                     case }: if(c!={) return false; break;
14                     case ): if(c!=() return false; break;
15                     case ]: if(c!=[) return false; break;
16                 }
17             }
18         }
19         if(!stk.empty()) return false;
20         return true;
21     }
22 };

better solution:

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         stack<char> paren;
 5         for (char& c : s) {
 6             switch (c) {
 7                 case (: 
 8                 case {: 
 9                 case [: paren.push(c); break;
10                 case ): if (paren.empty() || paren.top()!=() return false; else paren.pop(); break;
11                 case }: if (paren.empty() || paren.top()!={) return false; else paren.pop(); break;
12                 case ]: if (paren.empty() || paren.top()!=[) return false; else paren.pop(); break;
13                 default: ; // pass
14             }
15         }
16         return paren.empty() ;
17     }
18 };

 

20. Valid Parentheses(C++)