word_search.py

"""
Author : 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:
---------
|A|B|C|E|
|S|F|C|S|
|A|D|E|E|
---------

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.com/problems/word-search/

"""


defget_point_key(len_board: int, len_board_column: int, row: int, column: int) ->int:
"""
 Returns the hash key of matrix indexes.

 >>> get_point_key(10, 20, 1, 0)
 200
 """

returnlen_board*len_board_column*row+column


defexits_word(
board: list[list[str]],
word: str,
row: int,
column: int,
word_index: int,
visited_points_set: set[int],
) ->bool:
"""
 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
 """

ifboard[row][column] !=word[word_index]:
returnFalse

ifword_index==len(word) -1:
returnTrue

traverts_directions= [(0, 1), (0, -1), (-1, 0), (1, 0)]
len_board=len(board)
len_board_column=len(board[0])
fordirectionintraverts_directions:
next_i=row+direction[0]
next_j=column+direction[1]
ifnot (0<=next_i<len_boardand0<=next_j<len_board_column):
continue

key=get_point_key(len_board, len_board_column, next_i, next_j)
ifkeyinvisited_points_set:
continue

visited_points_set.add(key)
ifexits_word(board, word, next_i, next_j, word_index+1, visited_points_set):
returnTrue

visited_points_set.remove(key)

returnFalse


defword_exists(board: list[list[str]], word: str) ->bool:
"""
 >>> 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
board_error_message= (
"The board should be a non empty matrix of single chars strings."
 )

len_board=len(board)
ifnotisinstance(board, list) orlen(board) ==0:
raiseValueError(board_error_message)

forrowinboard:
ifnotisinstance(row, list) orlen(row) ==0:
raiseValueError(board_error_message)

foriteminrow:
ifnotisinstance(item, str) orlen(item) !=1:
raiseValueError(board_error_message)

# Validate word
ifnotisinstance(word, str) orlen(word) ==0:
raiseValueError(
"The word parameter should be a string of length greater than 0."
 )

len_board_column=len(board[0])
foriinrange(len_board):
forjinrange(len_board_column):
ifexits_word(
board, word, i, j, 0, {get_point_key(len_board, len_board_column, i, j)}
 ):
returnTrue

returnFalse


if__name__=="__main__":
importdoctest

doctest.testmod()