Ugly 52ms python solution


  • 0
    Z
    class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        lmore = 0
        rmore = 0
        lidx = []
        ridx = []
        count = 0
        for i in range(len(s)):
            if s[i] == '(':
                count += 1
            elif s[i] == ')':
                count -= 1
                if count < 0:
                    rmore += 1
                    count = 0
                    ridx.append(i)
        if count > 0:
            lmore = count
        if lmore == 0 and rmore == 0: return [s]    
        
        # case1: only ')' is more than '('.
        if rmore > 0 and lmore == 0:
            result = set()
            self.removeRight(result, s[:ridx[-1]+1], rmore, rmore, ridx, 0)
            return [l+s[ridx[-1]+1:] for l in list(result)]
        
        count = 0
        for i in range(-1,-len(s)-1,-1):
            if s[i] == ')':
                count += 1
            elif s[i] == '(':
                count -= 1
                if count < 0:
                    count = 0
                    lidx.append(i)
        # case2: only '(' is more than ')'.
        if lmore > 0 and rmore == 0:
            result = set()
            self.removeLeft(result, s[lidx[-1]:], lmore, lmore, lidx, -1)
            return [s[:lidx[-1]]+l for l in list(result)]
        
        # case3: in first interval, ')' is more than '('; in second interval, '(' is more than ')'.
        if lmore > 0 and rmore > 0:
            result1 = set()
            self.removeRight(result1, s[:ridx[-1]+1], rmore, rmore, ridx, 0)
            result2 = set()
            self.removeLeft(result2, s[lidx[-1]:], lmore, lmore, lidx, -1)
            return [l1+s[ridx[-1]+1:lidx[-1]]+l2 for l1 in list(result1) for l2 in list(result2)]
            
    def removeRight(self, result, s, c, n, ridx, idx):
        if n == 0:
            result.add(s)
            return
        for i in range(idx, ridx[0]+1-c+n):
            if s[i] == ')':
                ns = s[:i]+s[i+1:]
                self.removeRight(result, ns, c, n-1, ridx[1:], i)
        
    def removeLeft(self, result, s, c, n, lidx, idx):
        if n == 0:
            result.add(s)
            return
        for i in range(idx, lidx[0]-1+c-n, -1):
            if s[i] == '(':
                if i != -1:
                    ns = s[:i]+s[i+1:]
                else:
                    ns = s[:i]
                self.removeLeft(result, ns, c, n-1, lidx[1:], i)

Log in to reply
 

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