Given a string containing just the characters
'('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
The brackets must close in the correct order,
» Solve this problem"()"
and "()[]{}"
are all valid but "(]"
and "([)]"
are not.[解题思路]
经典的栈匹配。一个栈,左符号入栈,右符号出栈。最后检查栈是否为空。
[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:
Post a Comment