Python实现单词搜索

  • 题目要求：

  • 思路：

    • 先遍历数组，找到可能的起点

    • 定义一个helper函数，用来遍历当前起点的上下左右元素，看是否有符合给定单词的下一位的，如果又再递归调用helper函数

    • 当上下左右的下标越界或当前数组元素与当前的单词的字母不同时，返回False

  • 核心代码：

#遍历二维数组
for i in range(len(board)):
            for j in range(len(board[0])):
                   #调用helper函数
                if self.helper(board,i,j,word,0):
                    return True
        return False

#定义helper函数：
def helper(self,board,i,j,word,index):
        #如果当前的下标与单词的长度相等，说明前面的所有字母都找到了匹配，返回True
        if index == len(word):
            return True
        #如果当前的下标越界，或是当前的元素字母与单词中的字母不同，返回False
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[index]:
            return False
        #要把当前已经经过的数组元素标记
        board[i][j] = "*"
        #递归调用当前元素的上下左右，看有没有与单词的下一个字母相同的
        found = self.helper(board,i+1,j,word,index+1)\
                or self.helper(board,i,j+1,word,index+1)\
                or self.helper(board,i-1,j,word,index+1)\
                or self.helper(board,i,j-1,word,index+1)
        #已经标记的值要复原   
        board[i][j] = word[index]
        return found

  • 完整代码：

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.helper(board,i,j,word,0):
                    return True
        return False
    def helper(self,board,i,j,word,index):
        if index == len(word):
            return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[index]:
            return False
        board[i][j] = "*"
        found = self.helper(board,i+1,j,word,index+1)\
                or self.helper(board,i,j+1,word,index+1)\
                or self.helper(board,i-1,j,word,index+1)\
                or self.helper(board,i,j-1,word,index+1)
        board[i][j] = word[index]
        return found

以上是 Python实现单词搜索 的全部内容， 来源链接： utcz.com/a/14239.html

回到顶部