44ms Python solution


  • 8
    H
    • Scan from left to right, make sure count["("]>=count[")"].
    • Then scan from right to left, make sure count["("]<=count[")"].

    class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        removed = 0
        results = {s}
        count = {"(": 0, ")": 0}
        for i, c in enumerate(s):
            if c == ")" and count["("] == count[")"]:
                new_results = set()
                while results:
                    result = results.pop()
                    for j in range(i - removed + 1):
                        if result[j] == ")":
                            new_results.add(result[:j] + result[j + 1:])
                results = new_results
                removed += 1
            else:
                if c in count:
                    count[c] += 1
        count = {"(": 0, ")": 0}
        i = len(s)
        ll = len(s) - removed
        for ii in range(ll - 1, -1, -1):
            i-=1
            c = s[i]
            if c == "(" and count["("] == count[")"]:
                new_results = set()
                while results:
                    result = results.pop()
                    for j in range(ii, ll):
                        if result[j] == "(":
                            new_results.add(result[:j] + result[j + 1:])
                results = new_results
                ll -= 1
            else:
                if c in count:
                    count[c] += 1
        return list(results)

  • 0
    Y

    Very smart. Not sure how's the performance comparing with backtrack or dp solution.


  • 0
    H

    It beats 100% Python solutions :)


  • 0
    X

    Finally I understand it, then fall in love with it.


  • 0
    S

    The logic is so simple that i cant believe it works!


  • 1
    L

    I was baffled with the idea that when you do the right-left scan, you only lookup for ll = len(s) - removed characters, why is this the case?
    Or in other words, why do all the strings in results after left-right scan share the same right hand side substring?

    After some thoughts, I hypothesize this is due to the pattern of invalid parentheses can only be of the form ")(".


  • 0

    This algorithm keeps fast even when very bad situation, but it can be written more concisely.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.