BFS

Algorithms
bfs
Catalogue
  1. 1. Best First Search
    1. 1.1. 301. Remove Invalid Parentheses
      1. 1.1.1. Solution1. BFS
      2. 1.1.2. Solution2. DFS + pruning
  1. Init state
  2. expansion/generation rule
  3. termination

301. Remove Invalid Parentheses

  • BFS - level order traversal
  • remove the minimum number

Solution1. BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution(object):
    def removeInvalidParentheses(self, s):
        visited = set([s])
        queue = [s]
        res = []
        found = False
        while queue:
            for st in queue:
                if self.isValid(st):
                    found = True
                    res.append(st)

            if found: break
            nqueue = []
            for st in queue:
                for i, ch in enumerate(st):
                    if ch in "()":
                        nst = st[:i]+st[i+1:]
                        if nst not in visited:
                            nqueue.append(nst)
                            visited.add(nst)
            queue = nqueue
        return res

    def isValid(self, s):
        left = 0
        for ch in s:
            if ch == '(':
                left += 1
            elif ch == ')':
                left -= 1
                if left < 0:
                    return False
        return left == 0
  • We can also use dfs with pruning to solve this problem!

Solution2. DFS + pruning

  • Backtracking
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Solution(object):
        def removeInvalidParentheses(self, s):
            lp = rp = 0
            for ch in s:
                if ch == '(':
                    lp += 1
                elif ch == ')':
                    if lp > 0:
                        lp -= 1
                    else:
                        rp += 1
            res = set()
            self.dfs(lp, rp, 0, s, [], res)
            return list(res)

        def dfs(self, lp, rp, pairs, s, path, res):
            if lp < 0 or rp < 0 or pairs < 0:
                return

            if len(s) == 0:
                if lp == 0 and rp == 0 and pairs == 0:
                    res.add(''.join(path))
                return

            if s[0] == '(':
                self.dfs(lp-1, rp, pairs, s[1:], path, res)
                self.dfs(lp, rp, pairs+1, s[1:], path + [s[0]], res)
            elif s[0] == ')':
                self.dfs(lp, rp-1, pairs, s[1:], path, res)
                self.dfs(lp, rp, pairs-1, s[1:], path + [s[0]], res)
            else:
                self.dfs(lp, rp, pairs, s[1:], path + [s[0]], res)
Share