首页 > 代码库 > LeetCode --- 20. Valid Parentheses
LeetCode --- 20. Valid Parentheses
题目链接：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.
这道题的要求是检查括号是否匹配，其中字符串只包含‘(‘、‘)‘、‘{‘、‘}‘、‘[‘ 和 ‘]‘。
这道题的思路比较简单，用栈维护左括号，即在读取字符串的时候，遇到左括号就入栈。而在遇到右括号的时候，检测栈的状态，如果栈为空，说明没有与该右括号匹配的左括号，直接返回false；如果栈顶元素与该右括号不匹配，说明括号没有匹配，返回false；如果相匹配，这可以弹出栈顶元素，继续读取下一个字符了。
在判断括号是否匹配的时候，可以选择用if语句判断，也可以采用map实现。
时间复杂度：O(n)
空间复杂度：O(n)
1 class Solution
2 {
3 public:
4 bool isValid(string s)
5 {
6 stack<char> sc;
7 for(int i = 0; i < s.length(); ++ i)
8 {
9 if(s[i] == ‘(‘ || s[i] == ‘[‘ || s[i] == ‘{‘)
10 sc.push(s[i]);
11 else
12 {
13 if(sc.empty())
14 return false;
15
16 if((sc.top() == ‘(‘ && s[i] == ‘)‘) ||
17 (sc.top() == ‘[‘ && s[i] == ‘]‘) ||
18 (sc.top() == ‘{‘ && s[i] == ‘}‘))
19 sc.pop();
20 else
21 return false;
22 }
23 }
24
25 return sc.empty();
26 }
27 };转载请说明出处：LeetCode --- 20. Valid Parentheses
LeetCode --- 20. Valid Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。