首页 > 代码库 > LeetCode20——Valid Parentheses
LeetCode20——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.
题目大意:给定一个只包含‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and ‘]‘6种字符的字符串。判断一个输入字符串是否有效: 括号必须以正确的顺序关闭,如"()","()[]{}"是有效的,而"(]","([)]"是无效的。
难度系数:容易
分析下题意,首先从给出的例子可以看出,关闭顺序应该是:
最先出现的右括号应该与最此前最后出现的左括号对应。
理解了这个,就很容易发现,这跟栈很相似,把左括号一个个入栈,如果遇到右括号,弹出一个元素看看是否与之对应。扫描一遍字符串, 就可以得出结果来。我最终通过的代码如下:
bool isValid(string s) {
vector<char> vc;
map<char, char> em;
em[‘(‘] = ‘)‘;
em[‘{‘] = ‘}‘;
em[‘[‘] = ‘]‘;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == ‘(‘ || s[i] == ‘{‘ || s[i] == ‘[‘) {
vc.push_back(em[s[i]]);
} else if (vc.empty() || vc.back() != s[i]) {
return false;
} else {
vc.pop_back();
}
}
return vc.empty() ? true : false;
}
这个题还是容易的。来看看这题的运行时分布图:
总的来说,C++ < Python < Java。65个测试用例,全部通过,我的花费了2ms,还是可以的。
到目前为止,我做了3道题了。都是简单的,为什么不能一次提交通过呢?每次都觉得没问题,每次都出错。我想, 我考虑的不够周全,这也许是为什么bug不止的原因吧。那么,怎么尽可能地减少bug?测试用例尽可能覆盖全面。 突然发现,所谓0 bug的代码,这几乎是不可能的。
LeetCode20——Valid Parentheses
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。