题目

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1

输入: “()”
输出: true

示例 2

输入: “()[]{}”
输出: true

示例 3

输入: “(]”
输出: false

示例 4

输入: “([)]”
输出: false

示例 5

输入: “{[]}”
输出: true

来源：力扣（LeetCode）

题解

这道题我用了递归的思想，但是深究进去和其他的结题方法的本质还是一样的，也就是栈，后进先出，后发现的先匹配。每次遇到一个新的左括号就新进一个函数压一个栈。遇到匹配的合适的右括号就出栈并返回上层一个true，如果匹配到不合适的右括号，就返回false。如果在扫描到结束的时候还没有遇到匹配的括号，就返回false。

class Solution {
public:
    int length, index;
    string str;
    bool match() {
        char _match;
        bool valid = false;

        // 设置对当前括号匹配的右括号
        if (str[index] == '(') _match = ')';
        else if (str[index] == '[') _match = ']';
        else if (str[index] == '{') _match = '}';

        // 索引前进一步，开始对下一个符号进行分析
        index++;

        while (index < length) {
            if (str[index] == _match) { // 匹配成功
                index++;
                return true;
            } else if (str[index] == '(' || str[index] == '[' || str[index] == '{') { // 匹配到左括号
                if (!match()) return false;
            } else
                return false;
        }

        return false;
    }
    bool isValid(string s) {
        index = 0;
        length = s.length();
        str = s;
        while (index < length) {
            if (!match()) return false;
        }
        return true;
    }
};

这道题还有不用递归的栈。
不用递归的栈用起来要更简单一些（个人认为），这个情况下判断的是最后栈中是否还留有未匹配的符号，而不是检查是否匹配成功，这样的思想特别的有趣。

class Solution {
public:
    bool isValid(string s) {
        stack<char> stackk;
        for (char i: s) {
            if (i == '(' || i == '[' || i == '{') {
                stackk.push(i);
            } else {
                if (stackk.empty()) return false;
                if (stackk.top() + 1 == i || stackk.top() + 2 == i) {
                    stackk.pop();
                } else {
                    stackk.push(i);
                }
            }
        }
        return stackk.empty();
    }
};

结果

执行用时 : 4 ms, 在所有 C++ 提交中击败了83.45%的用户
内存消耗 : 8.7 MB, 在所有 C++ 提交中击败了67.22%的用户