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.

For example,
Given board=

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

word="ABCCED", -> returnstrue,

word="SEE", -> returnstrue,

word="ABCB", -> returnsfalse.

思路分析

这道题的基本思路是DFS（backtracking），但是该怎么下手呢？首先应该是要在board中找到word的第一个char，怎么找到第一个呢，就需要遍历整个board来找到word中的第一个char。找到了第一个char之后就要调用dfs来判断是不是整个word都在board中。当然word的第一个char可能在board中出现多次，所以我们要遍历board直到找到整个word返回True

在实现DFS函数的时候，每一个board中的字符会跟4个相邻的字符形成adjacency，所以DFS的方程中要包含这四个adjacency。同时要注意的是题目中要求每一个字符只能使用一次，所以找到字符后要将此字符转换为一个其他字符表明这个字符已经被使用过了。

DFS的退出条件是：

• 当word中的所有字符都找到了，也就是说word为空的时候就返回True
• 当index越界或者当前字符不是word的第一个字符的时候返回False

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if not board: return False
        for i in xrange(len(board)):
            for j in xrange(len(board[0])):
                if self.dfs(board, i, j, word): return True
        return False

    def dfs(self, board, row, col, word):
        if len(word) == 0: return True
        if row < 0 or row>=len(board) or col<0 or col>=len(board[0]) or board[row][col]!=word[0]: return False
        board[row][col] = "*"
        exist = self.dfs(board, row-1, col, word[1:]) or self.dfs(board, row+1, col, word[1:]) or self.dfs(board, row, col-1, word[1:]) or self.dfs(board, row, col+1, word[1:])
        board[row][col] = word[0]
        return exist