首页 > 代码库 > 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