Friday, January 11, 2013

[LeetCode] Valid Parentheses 解题报告


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.
» Solve this problem

[解题思路]
经典的栈匹配。一个栈,左符号入栈,右符号出栈。最后检查栈是否为空。

[Code]
1:    bool isValid(string s) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<char> sta;  
5:      if(s.size() ==0) return false;  
6:      sta.push_back(s[0]);  
7:      for(int i =1; i< s.size(); i++)  
8:      {  
9:        if(s[i] == '(' || s[i] == '[' || s[i] == '{')  
10:        {  
11:          sta.push_back(s[i]);  
12:          continue;  
13:        }  
14:        char current = sta.back();  
15:        if(s[i] == ')' && current != '(')  
16:          return false;  
17:        if(s[i] == ']' && current != '[')  
18:          return false;  
19:        if(s[i] == '}' && current != '{')  
20:          return false;  
21:        sta.pop_back();  
22:      }  
23:      if(sta.size() !=0) return false;  
24:      return true;  
25:    }  



No comments: