Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

301 Remove Invalid Parentheses #66

Open
tech-cow opened this issue Aug 14, 2019 · 5 comments
Open

301 Remove Invalid Parentheses #66

tech-cow opened this issue Aug 14, 2019 · 5 comments
Labels

Comments

@tech-cow
Copy link
Owner

No description provided.

@tech-cow tech-cow added the DFS label Aug 14, 2019
@tech-cow
Copy link
Owner Author

tech-cow commented Sep 19, 2019

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

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
Copy link
Owner Author

tech-cow commented Sep 20, 2019

优化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
Copy link
Owner Author

优化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
Copy link
Owner Author

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
Copy link
Owner Author

'''
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
            

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant