FilesExpand file tree

main

/

79-Word-Search.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

40 lines (33 loc) · 1.13 KB

main

/

79-Word-Search.py

Copy path

Top

File metadata and controls

• Code
• Blame

40 lines (33 loc) · 1.13 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

40

'''Leetcode- https://leetcode.com/problems/word-search/'''

'''

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: true

'''

# Solution

def exist(board, word):

ROWS, COLS = len(board), len(board[0])

path = set()

def dfs(r, c, i):

if i == len(word):

return True

if (r < 0 or c < 0 or

r >= ROWS or c >= COLS or

word[i] != board[r][c] or

(r, c) in path):

return False

path.add((r, c))

res = (dfs(r+1, c, i+1) or

dfs(r-1, c, i+1) or

dfs(r, c+1, i+1) or

dfs(r, c-1, i+1))

path.remove((r, c))

return res

for r in range(ROWS):

for c in range(COLS):

if dfs(r, c, 0):

return True

return False

#T: O(n*m*4^n)

#S: O(n)