Find a word in the grid
Decide whether a word can be traced through a grid of letters by stepping to neighbouring cells, using each cell at most once, by trying every start and every direction with backtracking. About 18 minutes.
Match a letter, then step
Write a function that asks: can I match the rest of the word, starting at this cell, with the letter at position i of the word? It fails at once if the cell is outside the grid or holds a different letter.
If the letter matches, the next letter must be found in one of the four neighbours. Try them one after another. If the whole word has been matched, the answer is yes.
if r < 0 or r >= rows or c < 0 or c >= cols:
return FalseA at the top left matches the first letter.
Mark, explore, unmark
A cell must not be used twice on one path. Before exploring from a cell, overwrite its letter with a marker such as a hash sign, so that no neighbour can match it again.
After the four tries return, restore the letter. Another path that starts elsewhere may need this cell. Try every cell as a start, and return yes if any start works.
ch = g[r][c] g[r][c] = "#" # mark g[r][c] = ch # unmark
Why is the marker removed after exploring from a cell?
- AOther paths may need to use that cell
- BTo make the search faster
- CTo change the letters
Show the answer
Other paths may need to use that cell. The mark should describe only the current path.
Word search
You are given a grid of letters board, given as an array of equal-length strings, and a string word. Return true if word can be formed by starting at any cell and moving, one letter at a time, to a cell directly above, below, left or right of the previous one, using each cell at most once.
board = ["ABCE", "SFCS", "ADEE"], word = "ABCCED" → true
1 ≤ rows, columns ≤ 6 · 1 ≤ length of word ≤ 15 · letters are upper case