[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.

中文解释

判断一个仅包含 小、中、大括号的字符串中的括号对是否匹配（以正确的顺序关闭）。

比如：“()”、“[]”、“{}”、“()[]{}”、“([])”是有效的，而“(]”、“([)]”等就是无效的。

题目解答

这种类型的题一看就知道应该用栈的方式来做，几乎不用考虑太多。

当遇到左括号时入栈，遇到相配对的右括号时出栈。当到达字符串结尾时栈为空（或说是与初始栈顶位置相同），即说明有效。

参考代码

说明：因为题目明确说明没有其它不相关字符（包括 '\0'），所以我采用了指针遍历的方式（c_str()），而不是元素迭代（begin(), end()），这样可能会提高一点效率。

版本1

class Solution {
public:
    bool isValid(string x) {
        std::stack<char> stk;
        const char* s = x.c_str();

        while(*s) {
            // 左括号入栈
            if(*s == '(' || *s == '[' || *s == '{') {
                stk.push(*s);
                s++;
            }
            // 右括号匹配时出栈
            else if(*s == ')' || *s == ']' || *s == '}') {
                if(!stk.empty() && (stk.top() == '(' && *s ==')' || stk.top() == '[' && *s == ']' || stk.top() == '{' && *s == '}')) {
                    stk.pop();
                    s++;
                }
                // 与栈顶括号不匹配，失败
                else {
                    return false;
                }
            }
            // 其它字符，无效
            else {
                return false;
            }
        }
    
        return stk.empty();
    }
};

正如前面所言，有效的条件应该是：到达输入字符串的结尾时 ①栈为空、②栈顶相同 时为有效。所以上面的代码有一个可以优化的地方：确保栈顶相同的就行，不需要每次都判断栈是否为空。于是：可以先压入一个不相关的字符，这样的话，栈就始终不为空了，不需要再 !stk.empty()。

版本2

class Solution {
public:
    bool isValid(string s) {
        std::stack<char> stk;
        const char* p;
    
        // 空串或奇数个数字符均无效
        if(s.empty() || s.size() & 1) {
            return false;
        }
    
        // 同样采用指针遍历
        p = s.c_str();

        // 先压入一个不相关的字符
        // 确保栈不为空，后面就需要检测了
        stk.push('.');
    
        while(*p) {
            switch(*p)
            {
            case '(':
            case '[':
            case '{':
                stk.push(*p);
                break;
    
            case ')':
                if(stk.top() == '(') {
                    stk.pop();
                    break;
                }
                else {
                    return false;
                }
    
            case ']':
                if(stk.top() == '[') {
                    stk.pop();
                    break;
                }
                else {
                    return false;
                }
    
            case '}':
                if(stk.top() == '{') {
                    stk.pop();
                    break;
                }
                else {
                    return false;
                }
            }
    
            p++;
        }
    
        // 由于前面压入了一个字符确保栈不为空
        // 所以这里应是判断是否为 1
        return stk.size() == 1;
    }
};

把 if 语句换成了 switch 语句，可能要清晰一点。

参考

1. Valid Parentheses | LeetCode OJ