推 oin1104: 寶 我好崇拜你 10/09 09:15
https://leetcode.com/problems/minimum-add-to-make-parentheses-valid
921. Minimum Add to Make Parentheses Valid
以下三種小括號字串是有效的:
1.空字串
2.只有英文字母的字串
3.(A) 就是左右括號這種樣子的字串
你可以在字串任何位置插入括號
請回傳使s變成有效字串的最小插入次數
思路:
stack 用stack存取字符
如若出現()這種狀況 就result-1
其他狀況代表要變動 result+1
Python Code:
class Solution:
def minAddToMakeValid(self, s: str) -> int:
if "(" not in s and ")" not in s:
return 0
result = 0
stack = []
for b in s:
if not stack:
stack.append(b)
result +=1
elif stack[-1] == "(" and b == ")":
stack.pop()
result -= 1
else:
stack.append(b)
result +=1
return result
感覺有更漂亮的寫法 但先這樣:))))
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728436341.A.142.html