20. 有效的括号

文|Seraph

01 | 问题

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

02 |解题

括号匹配，首先想到的就应该是使用栈，遇到左括号，则存储到栈中；遇到右括号，则取出栈中顶端值匹配，直到全部匹配。

初解：

map<char,char> mapA={
    {')','('},
    {'}', '{'},
    {']', '['}
};
bool isLeft(char ch)
{
    if(ch=='(' || ch=='{' || ch=='[')
        return true;
    return false;
}
class Solution {
public:
    bool isValid(string s) {
        stack<char> sk;
        size_t size = s.size();
        for(int i=0; i<size; i++)
        {
            if(isLeft(s[i]))
            {
                sk.push(s[i]);
            }
            else
            {
                if(sk.size() > 0)
                {
                     char temp = sk.top();
                      sk.pop();
                     if(mapA[s[i]] != temp)
                     {
                          return false;
                     }
                }
                else
                {
                    return false;
                }
               
            }
        }
        if(sk.size() > 0)
            return false;
        else
            return true;
    }
};

终解：

利用map中find函数可以减少isLeft函数的编写。

class Solution {
public:
    bool isValid(string s) {
        map<char,char> m;
        m[')'] ='(';
        m[']'] ='[';
        m['}'] ='{';
        stack<char> stack;
        for(auto &c :s){
            map<char,char>::iterator ret = m.find(c);
            if(ret == m.end())
                stack.push(c);
            else if(!stack.empty()){
                if((*ret).second != stack.top())
                    return false;
                stack.pop();
            }
            else
                return false;
        }
        return stack.empty();
    }
};

03 | 积累知识点

1. 注意stack的pop函数不返回值。