题目
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
例子
()-> true(]-> false([)]-> false[](){}-> True[{}]()-> True
假设
- 输入的字符串仅包含’(‘，’)’，’{‘，’}’，’[‘，’]’这些字符
tips
- 利用栈这一数据结构
答案
解法:
def isValid(s):
if len(s) % 2 == 1:
return False
pairs = {
")": "(",
"]": "[",
"}": "{",
}
stack = list()
for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stack 性能
- 时间复杂度O(n)
- 空间复杂度O(n)
关键点
- 利用栈这一数据结构
拓展
import prettytable
class StackException(Exception):
def __init__(self, msg):
self.__msg = msg
def __str__(self):
print(self.__msg)
class Stack:
def __init__(self, __len):
self.__date = [] # 存储栈数据
self.__size = 10 # 初始栈的长度
self.__len = 0 # 记录栈中数据的数量
def push(self, value):
"""
向栈顶压入数据
:param value:
:return: 是否压入成功 True|False
"""
if not self.isFull():
# 表示栈还没有满，可以添加数据
self.__date.append(value)
self.__len += 1
return True
else:
try:
raise StackException('栈已经满了，不能添加数据！')
finally:
return False
def pop(self):
"""
返回并删除栈顶数据
:return:
"""
if not self.isEmpty():
self.__len -= 1
return self.__date.pop()
else:
try:
raise StackException('栈为空，没有数据可以返回')
finally:
return None
def top(self):
"""
返回栈元素
:return:
"""
if not self.isEmpty():
return self.__date[-1]
else:
try:
raise StackException('栈为空，没有数据可以返回')
finally:
return None
def isEmpty(self):
"""
判断栈是否为空
:return: bool True|False
"""
if self.__len == 0:
return True
else:
return False
def isFull(self):
"""
判断栈是否为满
:return: bool True|False
"""
if self.__len == self.__size:
return True
else:
return False
def __size(self):
"""
返回栈中的容量
:return:
"""
return self.__len
def __length(self):
"""
返回栈中数据的数量
:return:
"""
return self.__size
def __len__(self):
"""
可以使用len()方法查看栈的长度
:return:
"""
return self.__len
def __str__(self):
"""
使用print()方法打印栈
使用prettytable打印成表格形式
:return:
"""
sta = prettytable.PrettyTable()
sta.field_names = ['栈顶']
for i in range(self.__len):
sta.add_row(self.__date[-i])
return sta.__str__()
使用栈实现
def isValid(s):
"""
判断括号是否匹配
:param s:
:return:
"""
if len(s) % 2 == 1:
return False
pairs = {')': '(',
'}': '{',
']': '['}
stack = Stack(len(s))
for item in s:
if item in pairs and stack.top() == pairs.get(item):
stack.pop()
else:
stack.push(item)
return stack.isEmpty()