301. Remvoe Invalid Parenthesis

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses(and).

Example 1:

Input:
 "()())()"

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

Example 2:

Input:
 "(a)())()"

Output:
 ["(a)()()", "(a())()"]

Example 3:

Input:")("

Output: [""]

Facebook Variation: any solution that results in minimum removal of parentheses

Thoughts: 楼主用了一个3-pass的方法: 先从头到尾找close比open多的，移掉; 从尾到头找open比close多的，移掉; 然后最后一遍build

class Solution:
    def removeInvalidParentheses(self, s):
        cnt = 0
        idx = []
        ans = ''
        # forward to remove close first
        for i, c in enumerate(s):
            if c == '(':
                cnt += 1
            if c == ')':
                cnt -= 1
                if cnt < 0:
                    idx.append(i)
                    cnt = 0  # reset the cnt
        cnt = 0
        # reverse to remove open first
        for i, c in enumerate(s[::-1]):
            if c == ')':
                cnt += 1
            if c == '(':
                cnt -= 1
                if cnt < 0:
                    idx.append(len(s) - i - 1)
                    cnt = 0
        return ''.join([s[i] for i in range(len(s)) if i not in idx])

s1= Solution()
print(s1.removeInvalidParentheses(""))
print(s1.removeInvalidParentheses("("))
print(s1.removeInvalidParentheses(")"))
print(s1.removeInvalidParentheses("(()"))
print(s1.removeInvalidParentheses("(()))"))

Thoughts:

1. Expanding the set and test whether each combination is valid, once there is answer in the set , then return (we want the minimum edition)

Code: Python

class Solution:
    def removeInvalidParentheses(self, s):
        def isvalid(s):
            ctr = 0
            for c in s:
                if c == '(':
                    ctr += 1
                elif c == ')':
                    ctr -= 1
                    if ctr < 0:
                        return False
            return ctr == 0
        level = {s}
        while True:
            res = filter(isvalid, level)
            if res:
                return res
            level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}