Word Search

[chengchengxu15]

lintcode: https://www.lintcode.com/problem/123/?_from=collection&fromId=29

leetcode: https://leetcode.com/problems/word-search/

Description Given a 2D board and a string word, find if the string word exists in the grid.

The string 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.

1er time 07/12/2021

[chengchengxu15]

note:

need one more Recursive Function to verifier if we start at board[i][j], if we can find the word.

[chengchengxu15]

solution

class Solution:
    """
    @param board: A list of lists of character
    @param word: A string
    @return: A boolean
    """
    def exist(self, board, word):
        # write your code here
        k = len(word)
        if k == 0:
            return True
        n = len(board)
        if n == 0:
            return False

        m = len(board[0])
        if m == 0:
            return False

        dict_used = {}
        for i in range(n):
            for j in range(m):
                word_index = 0
                if self.find_word(board,word,word_index,(i,j),dict_used,n,m):
                    return  True
        return False

    def find_word(self,board,word,word_index,position,dict_used,n,m):

        if word_index >= len(word):
            return True

        i, j = position
        if i >= n or i < 0 or j >= m or j < 0:
            return False

        if (i,j) in dict_used:
            return False

        if board[i][j] != word[word_index]:    
            return False 

        dict_used[(i,j)] = 1

        if self.find_word(board,word,word_index +1,(i-1,j),dict_used,n,m) or self.find_word(board,word,word_index +1,(i,j-1),dict_used,n,m) or self.find_word(board,word,word_index +1,(i+1,j),dict_used,n,m) or self.find_word(board,word,word_index +1,(i,j+1),dict_used,n,m):
            return True

        else:
            del dict_used[(i,j)]
            return False