[数据结构与算法]LeetCode写题日志——20. 有效的括号

题目来自于LeetCode第20题——有效的括号
题目如下：

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合
每个右括号都有一个对应的相同类型的左括号。

示例1：

输入：s = “()”
输出：true

示例2：

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

示例3：

输入：s = “(]”
输出：false

看到题目的想法：
1.题目中的括号是成对出现的，二者有先后的配对关系；
2.通过配对关系就可以得到用pair；
3.一旦扯上了pair，那么很容易想到map，unordered_map；
4.因此省下来一个问题就是解决先后关系；
5.先后关系指的就是我如何判断左括号后括号。

算法原理：
栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；
建立哈希表构建左右括号对应关系：key左括号，value 右括号；这样查询 2个括号是否对应只需 O(1)时间复杂度；建立栈 stack，遍历字符串 s 并按照算法流程一一判断。

算法流程：
先判断元素的奇数偶数，如果是奇数，直接输出false；
如果 c 是左括号 ，则入栈 push；
否则通过哈希表判断括号对应关系，若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应，则提前返回 false。
提前返回 false。
提前返回优点：在迭代过程中，提前发现不符合的括号并且返回，提升算法效率。

复杂度分析
时间复杂度 O(N)：正确的括号组合需要遍历 1 遍 s；
空间复杂度 O(N)：哈希表和栈使用线性的空间大小。

接下来是C++代码：

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {  //判断奇数偶数个数
            return false;
        }
        unordered_map<char, char> pairs = {  //构建哈希表进行对应
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {  //for( : )使用，在前面博客写过用法
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
}；

这是一天中最浪漫的部分
等待世界被一束路灯无限拉长
路还很长，共勉。