LeeCode每日一题--有效的括号
【前言】坚持日更LeeCode刷题系列
不积跬步,无以至千里;不积小流,无以成江海。愿与诸君共勉！
【题目】20.有效的括号
题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例:
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
思路一:通过python中的列表实现类似栈的功能，实现方法通括号匹配问题。具体代码如下：
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
for i in range(len(s)): #可自行运行样例理解
if(s[i]=='('):
stack.append(')')
elif(s[i]=='['):
stack.append(']')
elif(s[i]=='{'):
stack.append('}')
else:
if(len(stack)==0 or s[i] != stack.pop()):
return False
if len(stack)==0: #即所有的括号都得到了匹配
return True
else:
return False
运行结果：
Notice:该括号有效包含大括号在小括号内等类似情况，与生活实际有偏差。
关于其中一些知识的链接：
算法图解
思路二:replace函数的妙用，要使括号有效，那么一定最里层为配对的括号，将该对括号replace，以此类推，若最后得到空串，则返回true，否则返回false。具体代码如下（参考自LeeCode评论区大神）：
class Solution:
def isValid(self, s):
while '{}' in s or '()' in s or '[]' in s:
s = s.replace('{}', '')
s = s.replace('[]', '')
s = s.replace('()', '')
return s == ''
运行结果：
关于其中一些知识的链接：
字符串中的replace方法
分享就到这里了，欢迎大家一起交流讨论。
注明：
题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
作者：Mingw_
