【leetcode刷题】T19-有效的括号

今天分享leetcode第19篇文章，也是leetcode第20题—有效的括号（Valid Parentheses），地址是：https://leetcode.com/problems/valid-parentheses/从本题开始，将开始解决栈相关的问题。【英文题目】（学习英语的同时，更能理解题意哟~）Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.An input string is valid if:Open brackets must be closed by the same type of brackets.Open brackets must be closed in the correct order.Note that an empty string is also considered valid.Example :Input: "()"
Output: true
【中文题目】给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例:输入: "()"
输出: true
【思路】我们可以使用栈保留左括号，每遇到一个右括号，从栈中弹出一个左括号，并判断是否和右括号对应。【代码】python版本class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        ls = []
        # 使用字典，节省代码，否则要分别判断括号对应关系
        d = {'}':'{', ')':'(', ']':'['}
        for si in s:
            if si in '([{':
                ls.append(si)
            else:
                # ls没有元素或者元素不匹配
                if len(ls) == 0 or d[si] != ls[-1]:
                    return False
                else:
                    ls.pop()
        return len(ls) == 0
C++版本class Solution {
public:
    bool isValid(string s) {
        stack<char> ls;
        map<char, char> d;
        // 使用字典，节省代码，否则要分别判断括号对应关系
        d['}'] = '{';
        d[')'] = '(';
        d[']'] = '[';
        for(char si:s){
            if(si == '{' or si == '(' or si == '[')
                ls.push(si);
            else{
                // ls没有元素或者元素不匹配
                if((ls.size() == 0) or (d[si] != ls.top()))
                    return false;
                // 弹出元素
                ls.pop();
            }  
        }
        return ls.size() == 0;
    }
};