leetcode算法题解 20题 python Ver.
题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
这个问题可以用堆栈的思路来解决，遍历字符串，把左括号不断的压入栈中，直到遇见右括号，去栈中判断最后一个被压入的左括号是否是对应的右括号，如果不是，返回False。最后查看栈中是否还有括号，如果有，那么返回False；如果没有，那么返回True。
由于python中的list数据类型，可以直接当做栈来使用。使用到的属性为：append（即为入栈），pop（即为出栈），其中list[-1]为栈顶，list[0]为栈底。
解答
情况分析
当字符串为空时
按照题意，应该是有效的。
if len(s) == 0:
return True
当字符串中只有右括号时
此时，栈为空，也会触发有效。所以应该加上一个判断条件来避免判断错误。
Sstack = []#list为栈
length = 0
if i == '{' or i == '(' or i =='[':
Sstack.append(i)#将括号压入栈中
else:
length += 1#记录右括号的数量
当字符串中右括号比左括号多时
例如：'{}()]]'
此时length这个变量起到作用，每出栈一个左括号，length就减1，当length=0且栈中元素为空同时满足时，便可以判定有效了。
代码
class Solution:
def isValid(self, s: str) -> bool:
Sstack = []
length = 0
if len(s) == 0:
return True
for i in s:
if i == '{' or i == '(' or i =='[':
Sstack.append(i)
else:
length += 1
if len(Sstack) != 0:
if i == '}' and Sstack[-1] == '{':
Sstack.pop()
length -= 1
if i == ']' and Sstack[-1] == '[':
Sstack.pop()
length -= 1
if i == ')' and Sstack[-1] == '(':
Sstack.pop()
length -= 1
return len(Sstack) == 0 and length == 0
通过截图
image-20200223154749719
复杂度
由于入栈出栈均为O(1)时间，整个程序仅有一个循环，所以时间复杂度应该为O(n)
联系方式
感谢阅读！如果您对本片博文有任何意见或者建议，请联系我。感谢不尽🙏
