题目描述

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

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

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

我的解法——DFS（AC）

类似于迷宫，递归回溯，这种要探究所有可能性的，特别是要倒退回来继续探索其他方向的，基本大多都是backtracking。
必然要对每一点的每一条路径进行深度遍历，遍历过程中一旦出现：
- 数组越界
- 该点已访问过
- 该点的字符和word对应的index字符不匹配
就要对该路径进行剪枝。
记得在失败后，把标识重置回去
时间复杂度O(n)，空间复杂度O(n)
Beat 36%

class Solution(object):
    def __init__(self):
        self.board = None
        self.word = None
        self.m = None
        self.n = None
        self.my = None
        
    def dfs(self, x, y, now):
        if(now == len(self.word)):
            return True
        elif(x >= 0 and x < self.m and y >= 0 and y < self.n and self.board[x][y] == self.word[now] and self.my[x][y] != 1):
            self.my[x][y] = 1
            res = self.dfs(x - 1, y, now + 1) or\
            self.dfs(x + 1, y, now + 1) or\
            self.dfs(x, y - 1, now + 1) or\
            self.dfs(x, y + 1, now + 1)
            self.my[x][y] = 0
            return res
        else:
            return False
        
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        self.board = board
        self.word = word
        self.m = len(board)
        self.n = len(board[0])
        self.my = [[0] * self.n for k in range(self.m)]
        
        for i in range(self.m):
            for j in range(self.n):
                if(self.dfs(i, j, 0) is True):
                    return True
                # print(self.my)
        return False

最优解法

由于英文字符范围是0~127，因此遍历某个字符后，进行c^=128操作，该字符在后续匹配中就不会再次匹配到，从而实现标记的效果。在回溯的时候需要将标记的字符还原。