Hard

Remove Invalid Parentheses

LAB

Remove the fewest parentheses to make s valid. Return all valid results sorted lexicographically.

EXAMPLES

Example 1

Input
{
  "s": "()())()"
}

Output
[
  "(())()",
  "()()()"
]

FUNCTION SHAPE

s: string→stringArray

SOLUTION NOTE

Refer to the parenthesis chapter for the isValid() function. This question seems difficult, but it actually can be solved with a straightforward brute force bfs. The hint to use BFS is in the 'minimum number of removals', because when bfs reaches a node, it is guaranteed to be at the shortest distance. The interesting part is we can model each node in this graph as a string of parenthesis, and we make edges between strings if you can reach the other by removing a parenthesis. The idea is given the original string, we brute force try removing all parenthesis in a bfs manner, until we find the level where there is a valid parenthesis string, and then return all valid parenthesis strings on that level.

Reveal reference solution +

pythonREFERENCE

def removeInvalidParentheses(self, s: str) -> List[str]:
    def isValid(s):
        stack = 0 # count of opening paren
        for c in s:
            if c == '(':
                stack += 1
            elif c == ')':
                if stack == 0: return False
                stack -= 1
            else:
                continue
        return stack == 0

    visited = set()
    q = deque([s])
    while q:
        res = []
        for _ in range(len(q)):
            curr = q.popleft()

            if curr in visited: continue
            visited.add(curr)

            if isValid(curr):
                res.append(curr)

            for i in range(len(curr)): # remove curr[i]
                q.append(curr[:i] + curr[i+1:])

        if res: return res

    return [-1]

TimeO(2^n)

SpaceO(2^n)

Open on LeetCode ↗