Description
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.
Example:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
描述
给定一个2D板和一个单词，找出该单词是否存在于网格中。
该单词可以由顺序相邻的单元的字母构成，其中“相邻”单元是水平或垂直相邻的单元。 相同的字母单元格不得多次使用。
思路
- 给定一个二维数组和一个单词，返回单词是否出现在字符中.
- 单词出现在数组中的意思是：以数组中的某一个位置为起点，画一条连续的线（方向任意，可上可下，可左可右，任何时候线都可以改变方向）
- 按此线段从开始到结尾的顺序，线段上的字符和单词的所有字符一一匹配.
- 我们生成一个同给定的二维数组相同大小的数组，用于记录当前位置是否访问过.
- 我们以数组中的每一个位置为起始点进行检查，看是否以该起始点有符合要求的字符串.
- 在检查的是否，如果当前位置S[row][col]没有被检查过且当前位置S[row][col]与要匹配的字符串中的字符T[i]相等，我们检查该点的上S[row-1][col]下S[row+1][col]左S[row][col-1]右S[row][col+1]四个点是否和T[i+1]相等.
- 若是,我们检查相等的点的上下左右四个点是否和T[i+2]相等.
- 如此递归下去，直到满足递归终止条件:
- 当前位置已经被检查过，返回False.
- 当前位置已经越界，返回False.
- 当前位置没有被检查过但不和需要匹配的字符相等，返回Fasle.
- 当前需要检查的字符串索引超过了需要匹配的字符串索引，返回Ture.
class Solution: def exist(self, board, word): """ :type board: List[List[str]] :type word: str :rtype: bool """ row, col = len(board), len(board[0]) ischecked = [[False for _ in range(col)] for _ in range(row)] for i in range(row): for j in range(col): if self.check(i, j, 0, ischecked, board, word): return True return False def check(self, row, col, index, ischecked, board, word): # 如果index等于word的长度，说明此时已经找完所有的字符，只有前面的字符通过了才会找下一个字符 # 说明所有的字符都通过，返回Ture if index == len(word): return True # 如果越界或者当前位置已经检查过了，则返回False if row >= len(board) or row < 0 or col >= len(board[0]) or col < 0 or ischecked[row][col]: return False # 如果当前位置没有被占用并且当前位置和要检查的字符不等，返回False if not ischecked[row][col] and board[row][col] != word[index]: return False # 通过了上面的所有条件，说明此时要检查的字符是相等的 # 记录此时的位置，表示已经检查过了. ischecked[row][col] = True # 检查右边一个字符 if self.check(row, col+1, index+1, ischecked, board, word): return True # 检查下边一个字符 if self.check(row, col-1, index+1, ischecked, board, word): return True # 检查左边一个字符 if self.check(row+1, col, index+1, ischecked, board, word): return True # 检查右边一个字符 if self.check(row-1, col, index+1, ischecked, board, word): return True # 清空已经检查的情况 ischecked[row][col] = False return False if __name__ == "__main__": so = Solution() res = so.exist([["a"]], "ab") print(res)
源代码文件在这里.
