棧的應用.

class Solution(object):def minAddToMakeValid(self, S):""":type S: str:rtype: int"""stack=[]for s in S:if s=='(':stack.append(s)else:if stack:if stack[-1]=='(':stack.pop()else:stack.append(s)else:stack.append(s)return len(stack)

?這種方法是O(n)時間復雜度,O(n)空間復雜度,其實沒有必要實現一個棧,因為右括號如果進入了棧就不可能再被消去了.所以就兩個變量記錄兩邊括號數就行了,空間復雜度為O(1):

class Solution(object):def minAddToMakeValid(self, S):""":type S: str:rtype: int"""left,right=0,0for s in S:if s=='(':left+=1else:if left>0:left-=1else:right+=1return left+right

?

轉載于:https://www.cnblogs.com/zywscq/p/10519261.html

總結

以上是生活随笔為你收集整理的Leetcode 921. Minimum Add to Make Parentheses Valid的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。