题目来源：
https://leetcode.com/problems/word-search/
题意分析：
给定一个子表板和一个一个词，返回这个词是否在子表版上。子表板之间只能水平和垂直相连，子表板中的字符只能访问一次。
题目思路：
这是一个典型的深度优先搜索。首先找到第一个字符，从这个字符开始进行深度优先搜索，搜索的时候要记得把已经搜索的记录为true。
代码（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 l = len(word) 9 if l == 0:10 return False11 m = len(board)12 if m == 0: return False13 n = len(board[0])14 visit = [[False for i in range(n)] for j in range(m)]15 def dfs(x,y,word):16 if len(word) == 0: return True17 if x > 0 and not visit[x-1][y] and board[x - 1][y] == word[0]:18 visit[x - 1][y] = True19 if dfs(x - 1,y,word[1:]):20 return True21 visit[x - 1][y] = False22 if y > 0 and not visit[x][y-1] and board[x][y-1] == word[0]:23 visit[x][y-1] = True24 if dfs(x,y-1,word[1:]):25 return True26 visit[x][y-1] = False27 if x + 1< m and not visit[x+1][y] and board[x+1][y] == word[0]:28 visit[x+1][y] = True29 if dfs(x+1,y,word[1:]):30 return True31 visit[x+1][y] = False32 if y + 1 < n and not visit[x][y + 1] and board[x][y + 1] == word[0]:33 visit[x][y + 1] = True34 if dfs(x,y + 1,word[1:]):35 return True36 visit[x][y + 1] = False37 return False38 for i in range(m):39 for j in range(n):40 if board[i][j] == word[0]:41 visit[i][j] = True42 if dfs(i,j,word[1:]):43 return True44 visit[i][j] = False45 return False46
转载请注明出处：