推 oinishere: 大師 我也是用index來stack 然後錯了 我不知道我怎麼 04/07 14:15
→ oinishere: 錯的 我想先打手槍了 04/07 14:15
→ Rushia: 好色喔 04/07 14:16
推 JIWP: 大師 04/07 14:17
推 SecondRun: 大師 04/07 14:20
678. Valid Parenthesis String
給你一個只包含 "(",")","*" 的字串s，"*" 可以是左括號、右括號或空字串，求出s是
否可以組成一個合法的括號表達式。
思路：
1.用兩個stack儲存左括號和*，如果遇到(或*就push，如果遇到)分以下情況：
* 如果left有可以用的(就把他pop出來匹配
* 否則如果extra有可以用的*就把他pop出來當成(
* 如果left和extra都沒有表示)無法匹配，提早返回False
2.判斷left還有沒有沒處理完的括號，一直不斷的從extra裡面pop，如果他的索引在
當前left的右邊的話就可以匹配，從left刪除一個括號。
3.最後判斷left是否可以被匹配完即可
py code：
----------------------------------------------
class Solution:
def checkValidString(self, s: str) -> bool:
extra = []
left = []
for i, c in enumerate(s):
if c == '(':
left.append(i)
elif c == ')':
if not left and not extra:
return False
if left:
left.pop()
else:
extra.pop()
else:
extra.append(i)
while left and extra:
i = extra.pop()
if i >= left[-1]:
left.pop()
return not left
----------------------------------------------
--
https://i.imgur.com/hqrJ7kl.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712470284.A.427.html