Jianbo Dai's

lc1249.移除无效的括号

 
  • Dec 07, 2020

题目链接

啊思路就是记录下无效括号的位置然后再原字符串中除去，但是为什么我怎么慢哦，原来是因为别人在重新生成字符串时是用列表切片方式的所以很快。这个算法的时间复杂度是O（N），空间复杂度是O（N）。

class Solution:
    def minRemoveToMakeValid1(self, s: str) -> str:
        redundant = list()
        stack = list()
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            elif s[i] == ")":
                if not stack:
                    redundant.append(i)
                else:
                    stack.pop()
        for idx in stack:
            redundant.append(idx)
        ans = ""
        for j in range(len(s)):
            if j not in redundant:
                ans += s[j]
        return ans

    def minRemoveToMakeValid2(self, s: str) -> str:
        removes = [-1]
        l_paren = []
        for i in range(len(s)):
            if s[i] == '(':
                l_paren.append(i)
            elif s[i] == ')':
                if len(l_paren) == 0:
                    removes.append(i)
                else:
                    l_paren.pop()
        removes = removes + l_paren + [len(s) + 1]

        ans = []
        for idx in range(len(removes) - 1):
            ans += s[removes[idx] + 1 : removes[idx + 1]]
        return ''.join(ans)
Search