Leetcode-79 Word Search

Posted on Edited on In ,

描述

在给定的 2D 平面 board 中搜索单词 word，可以在垂直相邻和水平相邻方向进行深度搜索，如果找到返回 True，否则返回 False。

1
2
3
4
5
6
7
8
9
10
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

测试用例

1
2
3
4
5
6
7
8
9
10
11
board =
[
  ['A','B','C','E'],
  ['S','F','A','S'],
  ['A','E','F','E']
]

# Case 0: word is an empty string, word = '', return false
# Case 1: genaral case - word = "ABFE", return true
# Case 2: take backtracking under advisement, word = "AEFBCAFE", return true.
# Case 3: word = "ADEF", return false

分析

这是一个经典的 DFS 问题，对于一个坐标 (x, y) 可以往四个方向进行搜索，分别是 (x+1, y), (x-1, y), (x, y+1), (x, y-1)。四个方向只要有一个方向搜索成功即可，搜索成功的条件是搜索深度 d == len(word)-1。而搜素失败的原因有很多：

  1. (x, y) 出界；
  2. (x, y) 已经使用过（题目要求每个坐标只能使用一次）；
  3. 当前的 (x, y) 对应的值和 word[d] 不相等。

根据以上分析，构造 dfs 函数需要的参数有 x, y 和 d，其中 d 表示搜索的深度。此外，还需要一个保存搜索过的坐标的辅助变量，这个变量可以放在全局。考虑搜索失败的情况，代码如下：

1
2
3
4
5
6
7
8
9
visited = set()
def dfs(x, y, d):
    if out_of_bound(x, y):
        return False
    if (x, y) in visited:
        return False
    if board[x][y] != word[d]:
        return False
    # TODO

如果当前坐标 (x, y) 满足条件 board[x][y] == word[d] 且 d == len(word) - 1 则搜索成功，代码如下

1
2
3
4
5
6
7
8
9
10
visited = set()
def dfs(x, y, d):
    if out_of_bound(x, y):
        return False
    if (x, y) in visited:
        return False
    if board[x][y] != word[d]:
        return False
    if d == len(word) - 1:
        return True

否则继续往当前坐标的四个方向深入搜索，同时将当前坐标加入到 visited 中，表示当前坐标已经访问过，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
visited = set()
def dfs(x, y, d):
    if out_of_bound(x, y):
        return False
    if (x, y) in visited:
        return False
    if board[x][y] != word[d]:
        return False
    if d == len(word) - 1:
        return True
    
    # continue dfs
    visited.add((x,y))
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    found = False
    for i in range(4):
        new_x = x + dx
        new_y = y + dy
        found = found or dfs(new_x, new_y, d+1)
    
    return found

如上，代码基本结构已经完成，大部分测试已经通过。但是， 考虑具有回溯情况的 Case 2 ，以上代码会失。这是因为如果坐标 (x,y) 的某个方向深入搜索多个步骤后失败，最终还会回到 (x, y) 上进行下一个方向的尝试，可是在进行下一个方向搜索时，上次的失败搜索并没有释放搜索过的坐标，导致有些坐标在本次搜索不能被访问，最终搜索失败。 所以，对于当前坐标的搜索，如果四个方向都搜索失败，则需要释放当前的 (x, y)，即 回溯。如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
visited = set()
def dfs(x, y, d):
    if out_of_bound(x, y):
        return False
    if (x, y) in visited:
        return False
    if board[x][y] != word[d]:
        return False
    if d == len(word) - 1:
        return True
    
    # continue dfs
    visited.add((x,y))
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    found = False
    for i in range(4):
        new_x = x + dx
        new_y = y + dy
        found = found or dfs(new_x, new_y, d+1)
    if not found:
        visited.remove((x, y))
    return found

代码实现

根据如上分析，代码实现如下（实现使用 used 数组保存访问过的坐标，和用集合 visited 功能一致）：

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
35
36
37
38
39
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not word:
            return False
        m, n = len(board), len(board[0])
        used = [[False] * n for _ in range(m)]
        def dfs(x, y, pos):
            # x, y out of bound
            if x < 0 or x >= m or y < 0 or y >= n:
                return False
            # word[pos] not equals to board[x][y]
            if word[pos] != board[x][y]:
                return False
            # (x, y) already used
            if used[x][y]:
                return False
            # pos == len(word)-1
            if pos == len(word) - 1:
                return True

            used[x][y] = True
            dx = [0, 1, 0, -1]
            dy = [1, 0, -1, 0]

            found = False 
            for i in range(4):
                new_x = x + dx[i]
                new_y = y + dy[i]
                found = found or dfs(new_x, new_y, pos+1)
            # backtrack
            if not found:
                used[x][y] = False
            return found

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

改进：

如上代码使用额外空间来记录访问过的坐标，以避免重复访问，有个技巧可以使用 O(1) 的空间记录访问过的节点。我们只需要用一个特殊符号如 “#” 将访问过的坐标值替换，勾勒出访问路径，并在当前坐标搜索完成后将原来的值替换回来即可。如下：

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
35
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not word:
            return False
        m, n = len(board), len(board[0])
        def dfs(x, y, pos):
            # x, y out of bound
            if x < 0 or x >= m or y < 0 or y >= n:
                return False
            # word[pos] not equals to board[x][y]
            if word[pos] != board[x][y]:
                return False
            # pos == len(word)-1
            if pos == len(word) - 1:
                return True

            orignal = board[x][y]
            board[x][y] = "#"
            dx = [0, 1, 0, -1]
            dy = [1, 0, -1, 0]

            found = False 
            for i in range(4):
                new_x = x + dx[i]
                new_y = y + dy[i]
                found = found or dfs(new_x, new_y, pos+1)
            # backtrack
            board[x][y] = orignal
            return found

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False