[数据结构与算法]Leetcode：有效地字符串

题目：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()” 输出：true
示例 2：

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

输入：s = “(]” 输出：false
示例 4：

输入：s = “([)]” 输出：false
示例 5：

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

解题思路：
解法1：
（1）如果字符串第一个就以)、]、}开头，或者字符串长度为奇数，直接return False。
（2）把字符串的遍历过程当做是入栈和出栈的过程，如果为左侧符号则入栈（存入列表），如果当前元素为右侧符号，则将其和列表的最后一位进行配对，如果可正常配对则表示括号闭合，列表中的最后一个元素出栈（pop）。
（3）入栈、出栈过程后，如果字符串是有效括号的话，列表应该为空，返回True。反之返回为False。

解法2：
（1）由于闭合的括号都是成对按顺序出现的，利用循环，依次把成对的{}、[]、()删除掉，看最后是否为空字符串。

代码：

class Solution:
    def isValid(self, s: str) -> bool:
        if s[0] in [')','}',']'] or len(s) % 2 == 1:
            return False
        left = []
        try:
            for i in s:
                if i in ['(', '[', '{']:
                    left.append(i)
                elif i == ')' and left[-1] == '(' or i == ']' and left[-1] == '[' or i == '}' and left[-1] == '{':
                    left.pop()
                else:
                    return False
        except IndexError:
            return False

        if not left:
            return True
        else:
            return False

    def isValid2(self, s: str) -> bool:
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('()', '')
            s = s.replace('{}', '')
            s = s.replace('[]', '')

        if not s:
            return True
        else:
            return False