Valid Parentheses
原题&翻译
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:
1 2 3 |
Input: "()" Output: true |
1 2 3 |
Input: "()[]{}" Output: true |
1 2 3 |
Input: "(]" Output: false |
1 2 3 |
Input: "([)]" Output: false |
1 2 3 |
Input: "{[]}" Output: true |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
class Solution { private: char over(char c){ if (c == ']') { return '['; } else if (c == ')') { return '('; } else { return '{'; } } public: bool isValid(string s) { stack <char>stk; for(auto v:s) { if(v == '(' || v == '[' || v == '{' ) { stk.push(v); } else { if(stk.size()==0) { return false; } if(stk.top() == over(v)) { stk.pop(); }else { return false; } } } if(stk.size()==0) { return true; } else { return false; } } }; |