Re: [閒聊] 每日leetcode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間1年前 (2024/04/07 14:11)推噓3(3推 0噓 2→)

留言5則, 4人參與討論串98/1548 (看更多)

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