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
1 class Solution { 2 public: 3 bool isValid(string s) { 4 stack<char>q; 5 for (int i = 0; s[i]; i++) { 6 if (s[i] == '(' || s[i] == '[' || s[i] == '{') 7 q.push(s[i]); 8 else if (s[i] == ')'||s[i]==']'||s[i]=='}') { 9 if (q.empty())return false; 10 char c = q.top(); 11 if (s[i] == ')') { 12 if (c == '(')q.pop(); 13 else 14 return false; 15 } 16 else if (s[i] == ']') { 17 if (c == '[')q.pop(); 18 else 19 return false; 20 } 21 else if (s[i] == '}') { 22 if (c == '{')q.pop(); 23 else 24 return false; 25 } 26 } 27 } 28 if (!q.empty())return false; 29 return true; 30 } 31 };