新农上路
- 积分
- 87
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2020-5-11
- 最后登录
- 1970-1-1
|
本楼: |
👍
0% (0)
|
|
0% (0)
👎
|
全局: |
👍 47% (48) |
|
52% (53) 👎 |
注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号
x
本帖最后由 ATPtennis 于 2021-11-29 22:15 编辑
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
# level = {"(a)())()"}
level = {s}
def isValid(s):
count = 0
for c in s:
if c == "(":
count += 1
elif c == ")":
count -= 1
if count < 0:
return False
return count == 0
while True:
valid = []
for ele in level:
if isValid(ele):
valid.append(ele)
if valid:
return valid
new_level = set()
# BFS
for ele in level:
for i in range(len(ele)):
new_level.add(ele[:i] + ele[i+1:])
level = new_level
上面这个代码一般情况是没问题的,比如 s = "(a)())()",这样删除一个最后会返回valid列表。但是如果s = "((",这情况整个while True也不会停啊,然后valid一直是空的,只有valid不空时才返回东西。那么最后结果""空字符串是如何返回的?
知道问题在哪了。比如当s = { "(" }时,
for ele in level:
for i in range(len(ele)):
new_level.add(ele[:i] + ele[i+1:])
这几行代码运行完,new_level = {""},而不是{}。
也就是说,一个字符串a当我们写a[:0]时,它返回的是一个空字符串"",这样理解对吗?
比如a = "1",那么a[:0] = a[1:] = "".是这样吗?
|
评分
-
查看全部评分
上一篇: 转码-概念题怎么刷下一篇: 苹果6个月力扣高频题
|