[LeetCode]题解（python）：079 Word Search

题目来源

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

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 be used more than once.

题意分析

Input:

　　:type board: List[List[str]]
　　:type word: str

Output:

:rtype: bool

Conditions:给出一个字符串，看这个字符串是否可以在board中找到，找到的条件是：在board可以连成一条直线，注意已经用过的元素不能再用。

题目思路

用dfs，每次遍历上下左右（注意边界）。避免使用过的元素再次使用，则可以将已经使用过的元素替换为“#”，在使用完之后再替换回来。

AC代码（Python）

 1 class Solution(object):
 2     def exist(self, board, word):
 3         """
 4         :type board: List[List[str]]
 5         :type word: str
 6         :rtype: bool
 7         """
 8         def dfs(x, y, word):
 9             if len(word) == 0:
10                 return True
11             
12             if x > 0 and board[x - 1][y] == word[0]:
13                 tmp = board[x][y]
14                 board[x][y] = '#'
15                 if dfs(x - 1, y, word[1:]):
16                     return True
17                 board[x][y] = tmp
18             
19             if y > 0 and board[x][y - 1] == word[0]:
20                 tmp = board[x][y]
21                 board[x][y] = '#'
22                 if dfs(x, y - 1, word[1:]):
23                     return True
24                 board[x][y] = tmp
25                 
26             if x < len(board) - 1 and board[x + 1][y] == word[0]:
27                 tmp = board[x][y]
28                 board[x][y] = '#'
29                 if dfs(x + 1, y, word[1:]):
30                     return True
31                 board[x][y] = tmp
32                 
33             if y < len(board[x]) - 1 and board[x][y + 1] == word[0]:
34                 tmp = board[x][y]
35                 board[x][y] = '#'
36                 if (dfs(x, y + 1, word[1:])):
37                     return True
38                 board[x][y] = tmp
39             
40             return False
41         
42         for i in range(len(board)):
43             for j in range(len(board[i])):
44                 if board[i][j] == word[0]:
45                     if dfs(i, j, word[1:]):
46                         return True
47         return False