301 Remove Invalid Parentheses

[tech-cow]

No description provided.

[tech-cow]

最原始粗暴的方法，直接所有可能性的去找，会有非常多的冗余。

DFS Base Case
只要index到底了，就走一遍isValid

在主方程跑完DFS以后，对得到的答案进行最少更改的检查

        for ele in self.res:
            max_len = max(max_len, len(ele))
        
        final = []
        for ele in self.res:
            if len(ele) == max_len:
                final.append(ele)
        return final

Brute Force

class Solution():
    def removeInvalidParentheses(self, s):
        self.res = set()
        max_len = 0
        self.dfs(0, [], s)
        
        
        '''
        After all backtracking, postprocess to find out
        the least modification
        '''
        
        for ele in self.res:
            max_len = max(max_len, len(ele))
        
        final = []
        for ele in self.res:
            if len(ele) == max_len:
                final.append(ele)
        return final
        

    def dfs(self, index, temp, s):
        ''' 
        backtracking all possible solution with 
        no pruning for sake
        
        :param temp: list
        '''
        if index == len(s):
            temp_s = ''.join(temp)
            if self.isValid(temp_s):
                self.res.add(temp_s)
            return
        
        temp.append(s[index])
        self.dfs(index + 1, temp, s)
        temp.pop()
        self.dfs(index + 1, temp, s)

        
    def isValid(self, s):   
        '''
        check if a pair of parenthesis is valid
        '''
        count = 0
        for char in s:
            if char == '(': 
                count += 1
            if char == ')':
                count -= 1
                if count < 0: 
                    return False
        return count == 0

[tech-cow]

优化1.

Brute Force的冗余，通过Pruning去省去一些重复计算。

思考的方式可以从需要最少被更改几次出发

计算出左右括号的个数差，然后用函数 change_needed 表示。 在Backtrack过程中，往temp里面增加元素的时候不需要更改这个函数，因为并没有删除任何函数，而在删减的过程中，减少这个函数。

这种方式可以对change_needed为负数的时候进行剪枝

if change_needed < 0:
    return

然后对左右括号和其他字符的区分，也进行了一边的剪枝。

优化代码

class Solution():
    def removeInvalidParentheses(self, s):
        left = right = change_needed = 0
        
        for char in s:
            if char == '(':
                left += 1
            elif char == ')':
                if left > 0:
                    left -= 1
                else:
                    right += 1
        
        change_needed = left + right
        self.res = set()
        self.dfs(0, [], s, change_needed)
        return self.res
        

    def dfs(self, index, temp, s, change_needed):
        if change_needed < 0:
            return
        
        if index == len(s):
            if change_needed == 0:
                temp_s = ''.join(temp)
                if self.isValid(temp_s):
                    self.res.add(temp_s)
            return
        
        if s[index] == '(' or s[index] == ')':
            temp.append(s[index])
            self.dfs(index + 1, temp, s, change_needed)
            temp.pop()
            self.dfs(index + 1, temp, s, change_needed - 1)
        else:
            temp.append(s[index])
            self.dfs(index + 1, temp, s, change_needed)
            temp.pop()

            
        
    def isValid(self, s):   
        '''
        check if a pair of parenthesis is valid
        '''
        count = 0
        for char in s:
            if char == '(': 
                count += 1
            if char == ')':
                count -= 1
                if count < 0: 
                    return False
        return count == 0
        

[tech-cow]

优化2:

把Temp的Array 变成了 String，减少了一些代码和速度

class Solution():
    def removeInvalidParentheses(self, s):
        left = right = change_needed = 0
        
        for char in s:
            if char == '(':
                left += 1
            elif char == ')':
                if left > 0:
                    left -= 1
                else:
                    right += 1
        
        change_needed = left + right
        self.res = set()
        self.dfs(0, '', s, change_needed)
        return self.res
        

    def dfs(self, index, temp, s, change_needed):
        if change_needed < 0:
            return
        
        if index == len(s):
            if change_needed == 0:
                if self.isValid(temp):
                    self.res.add(temp)
            return
        
        if s[index] == '(' or s[index] == ')':
            self.dfs(index + 1, temp + s[index] , s, change_needed)
            self.dfs(index + 1, temp, s, change_needed - 1)
        else:
            self.dfs(index + 1, temp + s[index] , s, change_needed)

            
        
    def isValid(self, s):   
        count = 0
        for char in s:
            if char == '(': 
                count += 1
            if char == ')':
                count -= 1
                if count < 0: 
                    return False
        return count == 0
        

[tech-cow]

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        left = right = 0
        for c in s:
            if c == "(":
                left += 1
            elif c == ")":
                if left == 0:
                    right += 1
                else:
                    left -= 1

        def dfs(depth, left, right, left_rem, right_rem, cur):
            if depth == len(s):
                if left == right and left_rem == right_rem == 0:
                    self.ans.add(cur)
                    return
            else:  
                if s[depth] == "(":
                    if left_rem > 0:   
                        dfs(depth + 1, left, right, left_rem - 1, right_rem, cur)
                    dfs(depth + 1, left + 1, right, left_rem, right_rem, cur + "(")  
                elif s[depth] == ")":
                    if right_rem > 0:  
                        dfs(depth + 1, left, right, left_rem, right_rem - 1, cur)
                    if left > right:  
                        dfs(depth + 1, left, right + 1, left_rem, right_rem, cur + ")")
                else:  
                    dfs(depth + 1, left, right, left_rem, right_rem, cur + s[depth])  

        self.ans = set()
        dfs(0, 0, 0, left, right, "")
        return list(self.ans)

[tech-cow]

'''
Start: 6:59
# @ [二刷]


Bug 1: findLeftRightDiff() takes exactly 1 arguement
    @ Bug
    def findLeftRightDiff(s):
    
    @ Fixed
    def findLeftRightDiff(self, s):


Bug 2:
    @ Bug
    else:
        self.dfsHelper(s, res, curLeft, curRight, leftDiff, rightDiff, index + 1, temp)

    @ Fixed
    else:
        self.dfsHelper(s, res, curLeft, curRight, leftDiff, rightDiff, index + 1, temp + s[index])
'''

class Solution(object):
    def removeInvalidParentheses(self, s):
        if not s: return [""]
        res = set()
        leftDiff, rightDiff = self.findLeftRightDiff(s)
        curLeft, curRight = 0, 0
        self.dfsHelper(s, res, curLeft, curRight, leftDiff, rightDiff, 0, "")
        return res
        
        
        

    def dfsHelper(self, s, res, curLeft, curRight, leftDiff, rightDiff, index, temp):
        if index == len(s):
            if curLeft == curRight and leftDiff == rightDiff == 0:
                res.add(temp)
                return
            
        else:
            if s[index] == '(':
                if leftDiff:
                    self.dfsHelper(s, res, curLeft, curRight, leftDiff - 1, rightDiff, index + 1, temp)
                self.dfsHelper(s, res, curLeft + 1, curRight, leftDiff, rightDiff, index + 1, temp + '(')
            
            elif s[index] == ')':
                if rightDiff:
                    self.dfsHelper(s, res, curLeft, curRight, leftDiff, rightDiff - 1, index + 1, temp)
                if curRight < curLeft:
                    self.dfsHelper(s, res, curLeft, curRight + 1, leftDiff, rightDiff, index + 1, temp + ')')
            else:
                self.dfsHelper(s, res, curLeft, curRight, leftDiff, rightDiff, index + 1, temp + s[index])
        
        
    
    def findLeftRightDiff(self, s):
        leftDiff, rightDiff = 0, 0
        for ch in s:
            if ch == '(':
                leftDiff += 1
            elif ch == ')':
                if leftDiff != 0:
                    leftDiff -= 1
                else:
                    rightDiff += 1
        return leftDiff, rightDiff