backtracking.word_search

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 a 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/

Functions

exits_word(→ bool)	Return True if it's possible to search for the word suffix
get_point_key(→ int)	Returns the hash key of matrix indexes.
get_word_path(→ list[tuple[int, int]] | None)	Return the path of the word in the board if it exists; otherwise, return None.
validate_board_and_word(→ None)
word_exists(→ bool)

Module Contents

backtracking.word_search.exits_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 for the word suffix starting from the word_index.

>>> exits_word([["A"]], "B", 0, 0, 0, set())
False

backtracking.word_search.get_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

backtracking.word_search.get_word_path(board: list[list[str]], word: str) → list[tuple[int, int]] | None

Return the path of the word in the board if it exists; otherwise, return None.

>>> board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
>>> get_word_path(board, "ABCCED")
[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 1)]
>>> get_word_path(board, "SEE")
[(1, 3), (2, 3), (2, 2)]
>>> get_word_path(board, "ABCB") is None
True
>>> get_word_path([["A"]], 123)
Traceback (most recent call last):
    ...
ValueError: The word parameter should be a string of length greater than 0.

backtracking.word_search.validate_board_and_word(board: list[list[str]], word: str) → None

>>> board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
>>> validate_board_and_word(board, "ABCCED")
>>> validate_board_and_word(board, "SEE")
>>> validate_board_and_word(board, "ABCB")
>>> validate_board_and_word([["A"]], "A")
>>> validate_board_and_word(
...    [["B", "A", "A"], ["A", "A", "A"], ["A", "B", "A"]], "ABB"
... )
>>> validate_board_and_word([["A"]], 123)
Traceback (most recent call last):
    ...
ValueError: The word parameter should be a string of length greater than 0.
>>> validate_board_and_word([["A"]], "")
Traceback (most recent call last):
    ...
ValueError: The word parameter should be a string of length greater than 0.
>>> validate_board_and_word([[]], "AB")
Traceback (most recent call last):
    ...
ValueError: The board should be a non-empty matrix of single-character strings.
>>> validate_board_and_word([], "AB")
Traceback (most recent call last):
    ...
ValueError: The board should be a non-empty matrix of single-character strings.
>>> validate_board_and_word([["A"], [21]], "AB")
Traceback (most recent call last):
    ...
ValueError: The board should be a non-empty matrix of single-character strings.

backtracking.word_search.word_exists(board: list[list[str]], word: str) → bool

>>> board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
>>> word_exists(board, "ABCCED")
True
>>> word_exists(board, "SEE")
True
>>> word_exists(board, "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-character strings.
>>> word_exists([], "AB")
Traceback (most recent call last):
    ...
ValueError: The board should be a non-empty matrix of single-character strings.
>>> word_exists([["A"], [21]], "AB")
Traceback (most recent call last):
    ...
ValueError: The board should be a non-empty matrix of single-character strings.