This is a classic problem of the application of stacks. The idea is, each time we meet a (, { or[, we push it to a stack. If we meet a ), } or ], we check if the stack is not empty and the top matches it. If not, return false; otherwise, we pop the stack. Finally, if the stack is empty, returntrue; otherwise, return false.
The code is as follows, very straight-forward.
1 class Solution { 2 public: 3 bool isValid(string s) { 4 stack<char> paren; 5 for (int i = 0; i < s.length(); i++) { 6 if (s[i] == '(' || s[i] == '{' || s[i] == '[') 7 paren.push(s[i]); 8 else if (s[i] == ')' || s[i] == '}' || s[i] == ']') { 9 if (paren.empty()) return false; 10 if (!match(paren.top(), s[i])) return false; 11 paren.pop(); 12 } 13 } 14 return paren.empty(); 15 } 16 private: 17 bool match(char s, char t) { 18 if (t == ')') return s == '('; 19 if (t == '}') return s == '{'; 20 if (t == ']') return s == '['; 21 } 22 };
