alexander pantyukhin date november 24 2022 task given an m x n grid of characters board and a string word return true if word exists in the grid the word can be constructed from letters of sequentially adjacent cells where adjacent cells are horizontally or vertically neighboring the same letter cell may not be used more than once example matrix abce sfcs adee word abcced result true implementation notes use backtracking approach at each point check all neighbors to try to find the next letter of the word leetcode https leetcode comproblemswordsearch returns the hash key of matrix indexes getpointkey10 20 1 0 200 return true if it s possible to search the word suffix starting from the wordindex exitsworda b 0 0 0 set false wordexistsa b c e s f c s a d e e abcced true wordexistsa b c e s f c s a d e e see true wordexistsa b c e s f c s a d e e abcb false wordexistsa a true wordexistsb a a a a a a b a abb false wordexistsa 123 traceback most recent call last valueerror the word parameter should be a string of length greater than 0 wordexistsa traceback most recent call last valueerror the word parameter should be a string of length greater than 0 wordexists ab traceback most recent call last valueerror the board should be a non empty matrix of single chars strings wordexists ab traceback most recent call last valueerror the board should be a non empty matrix of single chars strings wordexistsa 21 ab traceback most recent call last valueerror the board should be a non empty matrix of single chars strings validate board validate word returns the hash key of matrix indexes get_point_key 10 20 1 0 200 return true if it s possible to search the word suffix starting from the word_index exits_word a b 0 0 0 set false word_exists a b c e s f c s a d e e abcced true word_exists a b c e s f c s a d e e see true word_exists a b c e s f c s a d e e abcb false word_exists a a true word_exists b a a a a a a b a abb false word_exists a 123 traceback most recent call last valueerror the word parameter should be a string of length greater than 0 word_exists a traceback most recent call last valueerror the word parameter should be a string of length greater than 0 word_exists ab traceback most recent call last valueerror the board should be a non empty matrix of single chars strings word_exists ab traceback most recent call last valueerror the board should be a non empty matrix of single chars strings word_exists a 21 ab traceback most recent call last valueerror the board should be a non empty matrix of single chars strings validate board validate word
def get_point_key(len_board: int, len_board_column: int, row: int, column: int) -> int:
    

    return len_board * len_board_column * row + column


def exits_word(
    board: list[list[str]],
    word: str,
    row: int,
    column: int,
    word_index: int,
    visited_points_set: set[int],
) -> bool:
    

    if board[row][column] != word[word_index]:
        return False

    if word_index == len(word) - 1:
        return True

    traverts_directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    len_board = len(board)
    len_board_column = len(board[0])
    for direction in traverts_directions:
        next_i = row + direction[0]
        next_j = column + direction[1]
        if not (0 <= next_i < len_board and 0 <= next_j < len_board_column):
            continue

        key = get_point_key(len_board, len_board_column, next_i, next_j)
        if key in visited_points_set:
            continue

        visited_points_set.add(key)
        if exits_word(board, word, next_i, next_j, word_index + 1, visited_points_set):
            return True

        visited_points_set.remove(key)

    return False


def word_exists(board: list[list[str]], word: str) -> bool:
    

    
    board_error_message = (
        "The board should be a non empty matrix of single chars strings."
    )

    len_board = len(board)
    if not isinstance(board, list) or len(board) == 0:
        raise ValueError(board_error_message)

    for row in board:
        if not isinstance(row, list) or len(row) == 0:
            raise ValueError(board_error_message)

        for item in row:
            if not isinstance(item, str) or len(item) != 1:
                raise ValueError(board_error_message)

    
    if not isinstance(word, str) or len(word) == 0:
        raise ValueError(
            "The word parameter should be a string of length greater than 0."
        )

    len_board_column = len(board[0])
    for i in range(len_board):
        for j in range(len_board_column):
            if exits_word(
                board, word, i, j, 0, {get_point_key(len_board, len_board_column, i, j)}
            ):
                return True

    return False


if __name__ == "__main__":
    import doctest

    doctest.testmod()