首页 > 代码库 > [LeetCode] 20. Valid Parentheses
[LeetCode] 20. 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.
解法一: stack
1 class Solution { 2 public: 3 bool isValid(string s) { 4 unordered_set<char> left = {‘(‘, ‘[‘, ‘{‘ }; 5 unordered_set<char> right = {‘)‘, ‘]‘, ‘}‘ }; 6 unordered_map<char, char> ht = {{‘(‘,‘)‘}, {‘[‘, ‘]‘}, {‘{‘,‘}‘} }; 7 stack<char> stk; 8 bool ret = false; 9 10 for (int i = 0; i < s.size(); i++){11 if (left.count(s[i])){12 stk.push(s[i]);13 }else if(right.count(s[i])){14 // check empty !!15 if (!stk.empty() && ht[stk.top()] == s[i]){16 stk.pop();17 }else{18 return false;19 }20 }else{21 return false;22 }23 }24 25 return stk.empty();26 }27 };
博主在Linked-in面试中碰到过这題的简化版: 一个字符串只包含小括号 ‘(‘ 或者‘)‘, 检查括号匹配是否正确.
该简化版的解法, 可以直接用一个计数器, 而不需要堆栈:
bool matched(String s){ int left = 0; for (int i = 0; i < s.size(); i++){ if (s[i] == ‘(‘){ left++; continue; }else if (s[i] == ‘)‘){ if (left > 0){ left--; }else{ return false; } } } return left == 0; }
[LeetCode] 20. Valid Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。