Python recursion solution


  • 0

    The solution by my own. Welcome to any improvements. :)))))

    def removeInvalidParentheses(self, s):
        def splits(s,x):
            return s[0:x] + s[x+1:]
        def Remove(s,remove_num):
            if s in self.cache: return 0
            elif remove_num > self.minremove: return 0
            elif s and s[-1] == '(': Remove(s[:len(s)-1],remove_num + 1)
            elif s and s[0] == ')': Remove(s[1:],remove_num + 1)
            else:
                r, l, s_n = [], [], 0
                while len(r) >= len(l) and s_n <= len(s) - 1:
                    if s[s_n] == '(': r.append(s_n)
                    elif s[s_n] == ')': l.append(s_n)
                    s_n += 1
                if len(r) < len(l):
                    for x in l:
                        Remove(splits(s,x),remove_num + 1)
                elif len(r) > len(l):
                    for x in r:
                        Remove(splits(s,x),remove_num + 1)
                else:
                    if remove_num < self.minremove: self.final = [s]; self.minremove = remove_num
                    else: self.final.append(s)
            self.cache[s] = 1
        self.cache,self.minremove,self.final = {}, 1000000000000000, []
        Remove(s,0)
        return self.final

Log in to reply
 

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