In the puzzle-page kind of word search, a hidden word always runs in a straight line: pick a starting cell and one of the 8 compass directions (left, right, up, down, or any of the four diagonals), then read consecutive cells without turning. Words may run backwards or upwards.
Write word_in_line(board: list[str], word: str) -> bool. board is a rectangular grid given as m strings of length n. Return True if word can be read along some straight line of the board, and False otherwise.
board = [
"CATS",
"ORAE",
"WDXT",
]
word_in_line(board, "CAT") # True row 0, left to right
word_in_line(board, "TAC") # True same cells, right to left
word_in_line(board, "COW") # True column 0, top to bottom
word_in_line(board, "CRX") # True diagonal from (0, 0) down-right
word_in_line(board, "SAD") # True anti-diagonal from (0, 3) down-left
word_in_line(board, "TES") # True column 3, bottom to top
word_in_line(board, "CAR") # False C -> A -> R turns a corner
word_in_line(board, "TAT") # False a line never revisits a cell
Details:
wordhas at least one letter; a one-letter word is found if that letter appears anywhere.- Letters are compared exactly (case matters).
- Constraints:
1 <= m, n <= 400,len(word) <= 400.
Checking every start cell and direction letter by letter is O(m·n·8·len(word)), which is far too slow on a board of all as searching for "aaa…ab". Aim for roughly O(m·n) character work per direction.
Show hint
every straight line of the board is itself a string. If you had each row, column and diagonal as one string, what would you do with it?