LeetCode 20. Valid Parentheses解题报告

这道题是菜鸡开始刷题的时候碰到的第一个小坎儿。刚开始几次submmit都没有成功。经过几次错误分析,发现题目要求的正确的字符串有几个特点:

  • 字符个数为偶数

  • 正确的字符串不管内容如何排布,总会有成对的括号在一起,一步步消除这种成对的括号,以及因为消除出现的新的成对括号,整个字符串就会消空。

基于上面两个特点,我自己编写了一个解法,可以说是惨不忍睹。但还是要贴出来以与后来的别人的简洁解法作对比:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):

def isPare(self, before, next):
if before == '[' and next == ']':
return 1
if before == '{' and next == '}':
return 1
if before == '(' and next == ')':
return 1
return 0

def popPare(self, s):
i = 0
while len(s)> 2:
if self.isPare(s[i], s[i+1]):
s.pop(i)
s.pop(i)
if i == 0:
i = -1
else:
i = i - 2
i = i + 1
if i > len(s) - 2:
break
return s

def isValid(self, s):
"""
:param s: str
:return: bool
"""
s = list(s)
if len(s) % 2 != 0:
return False
s = self.popPare(s)
if len(s) != 2:
return False
elif self.isPare(s[0], s[1]):
return True
else:
return False

我写了三个函数,第一个是用来检测字符配对,但这个其实用一个简单的词典就能完成。。我真是傻。

第二个用来检测所给字符串中相邻的字符是否配对,配对则消去。

在消去字符的时候我刚开始用的是remove方法。。我发现这个remove方法是根据传入内容从左开始的,这意味着重复的字符串里,remove的可能是左边的重复字符。后来还是用了pop函数,用了pop函数的时候我竟然还没有想到这道题可以用stack来快速解决啊。。我真是傻。

第三个就是判断函数,没啥好说的。。

好了,下面贴一个别人的python答案,使用了stack,很简洁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
# @return a boolean
def isValid(self, s):
stack = []
dict = {"]":"[", "}":"{", ")":"("}
for char in s:
if char in dict.values():
stack.append(char)
elif char in dict.keys():
if stack == [] or dict[char] != stack.pop():
return False
else:
return False
return stack == []

前路还有很远。加油。

  • 本文作者: 大护法
  • 本文链接: https://todebug.com/leetcode-20/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 4.0 许可协议。转载请注明出处!
0%