301.-remove-invalid-parentheses.md

301. Remove Invalid Parentheses

{% tabs %} {% tab title="BFS" %}

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        
        level = {s} ## 直接取set 会break 字符
        while level:
            ans = [l for l in level if self.isValid(l) is True]
            if ans:
                return ans
            
            else:
                next_level = set()
                for l in level:
                    for i in range(len(l)):
                        if l[i] in "()": 
                            next_level.add(l[:i]+l[i+1:])
                level = next_level    
        
    def isValid(self, s):
        cnt = 0
        for c in s:
            if c == "(": cnt += 1
            elif c == ")": cnt -= 1
            if cnt < 0: return False  
        return cnt == 0

{% endtab %} {% endtabs %}