题号：20
难度：Easy
链接：https://leetcode.cn/problems/valid-parentheses

思路

通常括号匹配，都会用到栈。遇左进栈，遇右判断是否匹配以及出栈。

这里涉及到三对括号，如果用switch之类分情况判断，效率会比较低。

想到用map做一个左括号到右括号的映射，配对时以左括号为键，访问到相应的右括号，对比即可。

代码

#include <map>
#include <stack>
#include <string>

using std::string;
using std::stack;
using std::map;

class Solution {
public:
    bool isValid(string s) {
        int len = s.size();
        map<char,char> bracMap; //左右括号的映射
        bracMap['(']=')';
        bracMap['[']=']';
        bracMap['{']='}';

        stack<char> bracStack;
        for(char &prstChar:s){
            //遇左进栈
            if(prstChar=='('||prstChar=='['||prstChar=='{') bracStack.push(prstChar);
            //遇右检查
            else{
                if(bracStack.empty()) return false;//出栈或访问栈顶元素前，都要检查是否栈空
                if(bracMap[bracStack.top()]==prstChar) bracStack.pop(); //匹配，则弹出栈顶即可
                else return false; //不匹配，返回false，结束程序
            }
        }
        //栈底还有落单的括号，说明无效
        return bracStack.empty()?true:false;
    }
};

提交结果

结果不错。

题外话

评论区看到一位dalao用Python写的解：

class Solution:
    def isValid(self, s):
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('{}', '')
            s = s.replace('[]', '')
            s = s.replace('()', '')
        return s == ''

思路确实独特，但运行效率应该不佳。

另一位的评论比较有趣，也挺中肯（无贬义）：

思路无敌，效率无语。

全文完