LeetCode-share/1249-Minimum_Remove_to_Make_Valid_Parentheses.py at master · QuenLo/LeetCode-share · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:

        slist = list(s)
        queue = []

        for ind, c in enumerate(s):
            if c == "(":
                queue.append(ind)
            if c == ")":

                if not queue:
                    slist[ind] = ""
                    continue
                queue.pop()

        for i in queue:
            slist[i] = ""


        return "".join( slist )

class SolutionII:
    def minRemoveToMakeValid(self, s: str) -> str:

        queue = []
        need_remove = []
        ans_str = ""

        for ind, s_char in enumerate(s):
            if s_char not in "()":
                continue
            if s_char == "(":
                queue.append( ind )
            elif not queue:
                need_remove.append( ind )
            else:
                queue.pop()

        need_remove.extend( queue )
        for ind, c in enumerate(s):
            if ind not in need_remove:
                ans_str += c

        return ans_str