A 68ms Python Solution by BFS and some optimization


  • 0
    A
    class Solution(object):
        def removeInvalidParentheses(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            degree = self.validDegree(s)
            if degree == 0:
                return [s]
            index = 0
            while index < len(s) and s[index] == ')':
                index += 1
            initIndex = index
            preIndex = index
            count = 0
            while index < len(s):
                if s[index] == '(':
                    count += 1
                    index += 1
                elif s[index] == ')':
                    count -= 1
                    index += 1
                    if count < 0:
                        count = 0
                        while index < len(s) and s[index] != '(':
                            index += 1
                        preIndex = index
                else:
                    index += 1
            leftPart = self.cur(s[initIndex:preIndex], set([]), ')', self.validDegree(s[initIndex:preIndex]))
            rightPart = self.cur(s[preIndex:], set([]), '(', self.validDegree(s[preIndex:]))
            result = []
            for r1 in leftPart:
                for r2 in rightPart:
                    result.append(r1+r2)
            return result
        def cur(self, s, oldStr, validChr, degree):
            if degree == 0:
                if self.validDegree(s) == 0:
                    return [s]
                else:
                    return []
            else:
                result = []
                for i, c in enumerate(s):
                    if c == validChr:
                        nextStr = s[0:i]+s[i+1:]
                        if nextStr not in oldStr:
                            tmpResult = self.cur(nextStr, oldStr, validChr, degree - 1)
                            oldStr.add(nextStr)
                            for res in tmpResult:
                                result.append(res)
            return result
        def validDegree(self, s):
            count = 0
            stack = []
            for c in s:
                if c == '(':
                    stack.append(c)
                elif c == ')':
                    if stack != []:
                        stack.pop()
                    else:
                        count += 1
            count += len(stack)
            return count

Log in to reply
 

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