【LeetCode】20.有效的括号

• 问题描述
• 我自己写的栈
• 标答写的栈

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

• 1 <= s.length <= 104
• s 仅由括号 ‘()[]{}’ 组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

这道题用栈做还是很简单的，附一下代码吧：

class Solution {
public:
	bool isValid(string s) {
		//建立括号对应关系的map
		unordered_map m;
		m['('] = ')';
		m['['] = ']';
		m['{'] = '}';
		//建立计算栈
		stack st;
		//进行计算和查找
		int length = s.size();
		for (int i = 0; i < length; i++) {
			if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
				st.push(s[i]);
			}
			else {
				if (st.size() != 0 && m[st.top()] == s[i]) {
					st.pop();
				}
				else {
					return false;
				}
			}
		}
		if (st.size() == 0) {
			return true;
		}
		else {
			return false;
		}
	}
};

结果：

关于需要注意的点，主要就是何时返回false（栈已经为空而字符串还没遍历完 or 右括号与栈顶的左括号不匹配），何时返回true（栈已经为空且各个括号都匹配上了）。

呃，不看不知道，一看吓一跳，以为自己已经写的很好了。看完标答之后发现还是有很多改进的地方的。下面直接把答案附上吧。

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

下面来列一下标答里的优点：

1. 对于一些特殊的错误情况，如果很好判断的话就先把它判断了直接返回。这样会节省很多时间！！！在这里就是先对字符串长度的奇偶进行判断，如果是奇数那肯定就是错了，直接返回false就行了；
2. 判断目前遇到的是左括号还是右括号，不要像我上面那样傻傻的枚举出来了，用一个map中的count()方法就行辽~
3. 最后出现的return stk.empty();还是可以学习一下噢，挺简洁的