8.16 - hard - 57

301. Remove Invalid Parentheses

这题很好,BFS的想法很奇特,去除最少的元素使得新的string合法,也就是说从不合法的s,找到所有最短路径(删除一个值就相当于一条边)的合法的new_s。解法就是把每一次删除的所有可能性列举出来,然后挨个挨个的检测。

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        level = {s}
        while True:
            valid = filter(self.isvalid, level)
            if valid:
                return valid
            level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
    
    def isvalid(self, s):
        ctr = 0
        for c in s:
            ctr += (c == '(') - (c == ')')
            if ctr < 0:
                return False
        return ctr == 0
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容