@Lin--
2020-02-05T05:27:50.000000Z
字数 948
阅读 369
Leetcode
题目分析:补充所需的左括号数或右括号数,使之能够凑成完整的括号对。
遍历字符组,若有相邻的一对,则不必补充;如果只是左括号,那么需要右括号。如果遇到右括号,若前面有左括号,则匹配消去一个。
左括号,否则需要一个左括号。最后将需要的左括号和有括号求和得需要括号数。
'''
# File: minAddToMakeValid.py
# Author: 0HP
# Date: 20200202
# Purpose: solve the problem in website: https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/
'''
class Solution:
def minAddToMakeValid(self, S: str) -> int:
Slength=len(S)
#empty string
if Slength==0:
return 0
index,left,right=0,0,0
#left meaning "(",need ")"
#right meaning ")", which can cancel left "(" if it exist before ")"
while index<Slength:
#when index not point the last char
if index<Slength-1:#if it exist "()"
if S[index]=='(' and S[index+1]==')':
index+=2
elif S[index]=='(' and S[index+1]=='(':
left+=1
index+=1
#when it be ")"
else:
#exist ")",cancel one ")"
if left>0:
left-=1
index+=1
#not exist, right+
else:
right+=1
index+=1
#the last char
else:
if S[index]=='(':
left+=1
index+=1
else:
if left>0:
left-=1
index+=1
else:
right+=1
index+=1
return left+right
t=Solution()
S="()()"
print(t.minAddToMakeValid(S))