Word Search

Posted on | Edited on | In | | Views:

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not used more than once.

题目的意思是, 给一个2d的数组, 和一个字符串, 要求返回数组里面是否可以由相邻的字母组成这个字符串.
例子如下: 

[
    [A, B, C, E]
    [S, F, C, S]
    [A, D, E, E]
]

word = ABCCED -> true

ABCCED 可以由 (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2) -> (2, 1) 组成.

思路

通常来说, 遇到2d数组找东西的题目, 脑海里面首先出现3种思路, DFS, BFS 或者 DP. 然后再分析哪一种更合适. 就这道题目来说, 首先想到的解法是DFS. 从(0, 0)开始, 到(m, n). 如果当前数组里面的字符跟目标字符一样, 那么用递归的方法搜索当前位置的上, 下, 左, 右看是否有合适的字符. 这里需要注意一点, 同一个点的字符不能使用两次, 所以我们还需要额外再维护一个数组来记录当前的点是否被使用过.

有了以上的思路, 再结合DFS的模板, 稍作修改, 就可以得到这道题的解法.

Code

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
def exist(board, word):
    if not word:
        return False
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] == word[0]:
                if self.dfs(board, word, i, j, []):
                    return True
    return False

def dfs(board, word, x, y, visited):
    if len(word) == 0:
        return False
    if (x, y) in visited:
        return False
    
    if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]):
        return False
    
    if board[x][y] != word[0]:
        return False
    
    else:
        visited.append((x, y))
    
    up = self.dfs(board, word[1:], x+1, y, visited)
    down = self.dfs(board, word[1:], x-1, y, visited)
    left = self.dfs(board, word[1:], x, y-1, visited)
    right = self.dfs(board.word[1:], x, y+1, visited)

    if not (up or down or left or right):
        visited.pop()
        return False
    return True

复杂度

$O(n \cdot m)$, m为2d数组的行数, n为2d数组的列数

EOF