[LeetCode]Remove Invalid Parentheses

题目描述:

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

题目大意:

移除最小数量的无效括号,使得输入字符串有效。返回所有可能的结果。

注意:输入字符串除了左右小括号外,还可能包含字母。

测试样例见题目描述。

解题思路:

解法I:深度优先搜索(DFS)+剪枝(Pruning)

利用评价函数计算字符串中未匹配括号的个数

尝试从输入字符串中移除括号,若得到的新字符串的失配括号比原字符串少,则继续搜索;

否则剪枝。

Python代码(DFS + 剪枝):

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        def dfs(s):
            mi = calc(s)
            if mi == 0:
                return [s]
            ans = []
            for x in range(len(s)):
                if s[x] in ('(', ')'):
                    ns = s[:x] + s[x+1:]
                    if ns not in visited and calc(ns) < mi:
                        visited.add(ns)
                        ans.extend(dfs(ns))
            return ans    
        def calc(s):
            a = b = 0
            for c in s:
                a += {'(' : 1, ')' : -1}.get(c, 0)
                b += a < 0
                a = max(a, 0)
            return a + b

        visited = set([s])    
        return dfs(s)

注释:

上述代码中的calc函数统计字符串s中包含的失配括号数目。

其中,变量a统计失配的左括号数目,变量b统计失配的右括号数目。

解法II:广度优先搜索(BFS)

参考:https://leetcode.com/discuss/67842/share-my-java-bfs-solution

通过从输入字符串中移除每一个括号,生成新的字符串加入队列。

如果从队列中取出的字符串是有效的,则加入结果列表。

一旦发现有效的字符串,则不再向队列中补充新的可能字符串。

根据BFS的性质,当首次从队列中发现有效字符串时,其去掉的括号数一定是最小的。

而此时,队列中存在的元素与队头元素去掉的括号数的差值 ≤ 1

并且,只有与队头元素去掉括号数目相同的元素才有可能是候选答案(根据括号匹配的性质可知)。

Python代码(BFS):

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        def isValid(s):
            a = 0
            for c in s:
                a += {'(' : 1, ')' : -1}.get(c, 0)
                if a < 0:
                    return False
            return a == 0

        visited = set([s])
        ans = []
        queue = collections.deque([s])
        done = False
        while queue:
            t = queue.popleft()
            if isValid(t):
                done = True
                ans.append(t)
            if done:
                continue
            for x in range(len(t)):
                if t[x] not in ('(', ')'):
                    continue
                ns = t[:x] + t[x + 1:]
                if ns not in visited:
                    visited.add(ns)
                    queue.append(ns)

        return ans

BFS也可应用解法I中的剪枝策略:

Python代码(BFS + 剪枝):

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        def calc(s):
            a = b = 0
            for c in s:
                a += {'(' : 1, ')' : -1}.get(c, 0)
                b += a < 0
                a = max(a, 0)
            return a + b

        visited = set([s])
        ans = []
        queue = collections.deque([s])
        done = False
        while queue:
            t = queue.popleft()
            mi = calc(t)
            if mi == 0:
                done = True
                ans.append(t)
            if done:
                continue
            for x in range(len(t)):
                if t[x] not in ('(', ')'):
                    continue
                ns = t[:x] + t[x+1:]
                if ns not in visited and calc(ns) < mi:
                    visited.add(ns)
                    queue.append(ns)

        return ans

 

本文链接:http://bookshadow.com/weblog/2015/11/05/leetcode-remove-invalid-parentheses/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论