LeetCode-20-有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

1 2	输入: "()" 输出: true

示例 2:

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

示例 3:

1 2	输入: "(]" 输出: false

示例 4:

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

示例 5:

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

Code

//时间复杂度O(N)
//空间复杂度O(N)
class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        bool res =true;
        int len = s.size(),idx=0;
        //字符串长度为奇数时直接返回false
        //空字符串处理
        if(len==0)
            return res;
        stk.push(s[idx]);
        //结束条件：括号全部删除，栈清空；或已经没有可用的字符了
        while(++idx<len){
            //判断左括号还是有括号
            if(s[idx]=='('||s[idx]=='['||s[idx]=='{')
                stk.push(s[idx]);
            else{
                if(stk.empty()){
                    res = false;
                    break;
                }else{
                    //匹配对应的括号
                    char c = stk.top();
                    if(match(c,s[idx]))
                        stk.pop();
                    else{
                        res = false;
                        break;
                    }
                }
            }
        }     
        if(!stk.empty())
            res=false;

        return res;
    }
    //匹配函数
    bool match(char top,char c){
        if((top=='('&&c==')')||(top=='['&&c==']')||(top=='{'&&c=='}'))
            return true;      
        else
            return false;
    }
};