一起刷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.

C++代码, 已AC. 写得有点冗长, 不知道C++里有没有像Python那样的contain()函数.
class Solution {
public:
    bool isValid(string s) {
        std::stack<char> ss;
        for(int i=0; i < s.length(); ++i)
            switch(s[i])
            {
                case '(':
                case '{':
                case '[':
                    ss.push(s[i]);
                    break;
                case ')':
                    if(ss.empty() || ss.top() != '(')
                        return false;
                    ss.pop();
                    break;
                case ']':
                    if(ss.empty() || ss.top() != '[')
                        return false;
                    ss.pop();
                    break;
                case '}':
                    if(ss.empty() || ss.top() != '{')
                        return false;
                    ss.pop();
                    break;
                default:
                    break;
                
            }
        if(ss.empty())
            return true;
        return false;
            
    }
};
已邀请:

beta

赞同来自: July geekeeper


再附一个别人的代码,鲁棒性比较好,代码也比较简练,

C++代码(已AC),时间复杂度 O(n) ,空间复杂度 O(n)
    class Solution {
    public:
        bool isValid(string const& s) {
            string left = "([{", right = ")]}";    //有兴趣的同学可以试试用哈希表存储左右结构
            stack<char> stk;
            for (auto c : s) {
                if (left.find(c) != string::npos) {
                    stk.push(c);
                }
                else {
                    if (stk.empty() || stk.top() != left[right.find(c)])
                        return false;
                    else
                        stk.pop();
                }
            }
            return stk.empty();
        }
    };

要回复问题请先登录注册