word_search

View Source

 1# @leet start
 2class Solution:
 3    def exist(self, board: list[list[str]], word: str) -> bool:
 4        """
 5        This question can be solved with backtracking.
 6        We can DFS through the board, just remembering to backtrack from the visited
 7        set after we realize that this board can't contain the word.
 8        """
 9        m, n = len(board), len(board[0])
10
11        def inbounds(y, x):
12            return 0 <= y < m and 0 <= x < n
13
14        def search(word, visited, y, x):
15            if not word:
16                return True
17
18            if not inbounds(y, x) or (y, x) in visited or board[y][x] != word[0]:
19                return False
20
21            visited.add((y, x))
22            dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]
23
24            for dy, dx in dirs:
25                if search(word[1:], visited, dy + y, dx + x):
26                    return True
27
28            visited.remove((y, x))
29
30        for y in range(m):
31            for x in range(n):
32                if search(word, set(), y, x):
33                    return True
34
35        return False
36
37
38# @leet end
39
40
41def test():
42    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def exist(self, board: list[list[str]], word: str) -> bool:
 5        """
 6        This question can be solved with backtracking.
 7        We can DFS through the board, just remembering to backtrack from the visited
 8        set after we realize that this board can't contain the word.
 9        """
10        m, n = len(board), len(board[0])
11
12        def inbounds(y, x):
13            return 0 <= y < m and 0 <= x < n
14
15        def search(word, visited, y, x):
16            if not word:
17                return True
18
19            if not inbounds(y, x) or (y, x) in visited or board[y][x] != word[0]:
20                return False
21
22            visited.add((y, x))
23            dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]
24
25            for dy, dx in dirs:
26                if search(word[1:], visited, dy + y, dx + x):
27                    return True
28
29            visited.remove((y, x))
30
31        for y in range(m):
32            for x in range(n):
33                if search(word, set(), y, x):
34                    return True
35
36        return False

def exist(self, board: list[list[str]], word: str) -> bool: View Source

 4    def exist(self, board: list[list[str]], word: str) -> bool:
 5        """
 6        This question can be solved with backtracking.
 7        We can DFS through the board, just remembering to backtrack from the visited
 8        set after we realize that this board can't contain the word.
 9        """
10        m, n = len(board), len(board[0])
11
12        def inbounds(y, x):
13            return 0 <= y < m and 0 <= x < n
14
15        def search(word, visited, y, x):
16            if not word:
17                return True
18
19            if not inbounds(y, x) or (y, x) in visited or board[y][x] != word[0]:
20                return False
21
22            visited.add((y, x))
23            dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]
24
25            for dy, dx in dirs:
26                if search(word[1:], visited, dy + y, dx + x):
27                    return True
28
29            visited.remove((y, x))
30
31        for y in range(m):
32            for x in range(n):
33                if search(word, set(), y, x):
34                    return True
35
36        return False

This question can be solved with backtracking. We can DFS through the board, just remembering to backtrack from the visited set after we realize that this board can't contain the word.

def test(): View Source

42def test():
43    assert 2 + 2 == 4