题解 | #括号序列#

括号序列

http://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2

对应 Leetcode-20.有效的括号

看到这样的题目，涉及到对应的匹配，一般都会用stack的特性来实现，后入先出（LIFO）Last in, First out.

但是题目要求有几种特殊的情况需要考虑 :

case 1: 

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

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

case 3:
输入：s = "(]"
输出：false

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

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

其中特殊的情况是case 2和case 5是典型的两种特殊情况，需要考虑。

大概的思路就是 : 左边的括号先stack.push,如果遇到右边的括号需要判断栈顶stack.top 是否相等，如果不等则return false, 如果== 则 stack.pop, 最终看stack.empty() 是否为空，如果不为空，则括号不匹配。

题解

解决这种题目最好是用C++实现，毕竟使用C语言的逻辑会更加麻烦和复杂一些。C语言中没有现成的stack结构。

比如在面试的过程中，一眼看到这种题目，最容易想到的应该使用栈这种结构遍历判断，

需要注意的括号的匹配判断，这里使用一个tips，如果是左括号，需要把右括号 stack.push，不然会出现case 4 样例的bug，不知道stack 里面的括号匹配

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool isValid(string s) {
        // write code here
        stack<char> str;
        for(int i = 0; i<s.size(); i++){
            //这里使用一个tips，如果是左括号，需要把右括号 stack.push
            if(s[i] == '('){
                str.push(')');
            }else if(s[i] == '['){
                str.push(']');
            }else if(s[i] == '{'){
                str.push('}');
            }else if(str.empty() || str.top() != s[i]){
                // 判断右边的括号是否和str.top()相等
                return false;
            }else{
                str.pop();
            }
        }
        return str.empty();
    }
};

官方的题解的效率会更高。其中括号的匹配搜索使用unordered_map的结构存储来进行遍历

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool isValid(string s) {
        // write code here
        if(s.size()%2 == 1){
            return false;
        }
        stack<char> str;
        unordered_map<char, char> hash_map = {
            {')','('},
            {'}','{'},
            {']','['}
        };

        for(char ch : s){
            //统计key值在unordered_map中出现的次数。实际上，c++ unordered_map不允许有重复的key。因此，如果key存在，则count返回1，如果不存在，则count返回0.
            if(hash_map.count(ch)){
                if(str.empty() || str.top() != hash_map[ch]){
                    return false;
                }
                str.pop();
            }else{
                str.push(ch);
            }
        }
        return str.empty();
    }
};

思考过程 :

刚开始看到题目，并没有大概的思路，总是在纠结case 2 以及 case 5的情况，没有好的思路，看了别人的讲解之后，恍然大雾，其实核心的判断原则就是 : **左边的括号先stack.push,如果遇到右边的括号需要判断栈顶stack.top 是否相等，如果不等则return false, 如果== 则 stack.pop, 最终看stack.empty() 是否为空，如果不为空，则括号不匹配。

参考题解:

以上的记录属于解题过程中一些记录，如果侵权，请联系我删除。