[关闭]
@Lin-- 2020-02-05T05:27:50.000000Z 字数 948 阅读 369

minAddToMakeValid

Leetcode


题目分析:补充所需的左括号数或右括号数,使之能够凑成完整的括号对。
遍历字符组,若有相邻的一对,则不必补充;如果只是左括号,那么需要右括号。如果遇到右括号,若前面有左括号,则匹配消去一个。
左括号,否则需要一个左括号。最后将需要的左括号和有括号求和得需要括号数。

  1. '''
  2. # File: minAddToMakeValid.py
  3. # Author: 0HP
  4. # Date: 20200202
  5. # Purpose: solve the problem in website: https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/
  6. '''
  7. class Solution:
  8. def minAddToMakeValid(self, S: str) -> int:
  9. Slength=len(S)
  10. #empty string
  11. if Slength==0:
  12. return 0
  13. index,left,right=0,0,0
  14. #left meaning "(",need ")"
  15. #right meaning ")", which can cancel left "(" if it exist before ")"
  16. while index<Slength:
  17. #when index not point the last char
  18. if index<Slength-1:#if it exist "()"
  19. if S[index]=='(' and S[index+1]==')':
  20. index+=2
  21. elif S[index]=='(' and S[index+1]=='(':
  22. left+=1
  23. index+=1
  24. #when it be ")"
  25. else:
  26. #exist ")",cancel one ")"
  27. if left>0:
  28. left-=1
  29. index+=1
  30. #not exist, right+
  31. else:
  32. right+=1
  33. index+=1
  34. #the last char
  35. else:
  36. if S[index]=='(':
  37. left+=1
  38. index+=1
  39. else:
  40. if left>0:
  41. left-=1
  42. index+=1
  43. else:
  44. right+=1
  45. index+=1
  46. return left+right
  47. t=Solution()
  48. S="()()"
  49. print(t.minAddToMakeValid(S))
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注