Find every word on a letter grid
You get a grid of lowercase letters board (a list of rows, each a list of one-letter strings) and a list words in which no word appears twice. A word is on the board if you can spell it by starting at some cell and stepping, one letter at a time, to a cell directly above, below, left or right of the current one (never diagonally), without using any cell twice in that word.
Return a list of every word from words that is on the board, each word once, in any order. Leave board as you found it: if you change cells while searching, put them back before you return.
This problem combines the trie from module 9 with the grid walk from module 11's Word Search, which marks each cell on the way in and puts it back on the way out. If you have not reached module 11, come back after it.
board = [["a", "b"], ["c", "d"]], words = ["abdc", "aba"]Output["abdc"]"abdc" walks around the square: a, right to b, down to d, left to c. "aba" would need the same a twice.
board = [["c", "a", "t"], ["o", "r", "e"], ["d", "o", "g"]], words = ["cat", "dog", "rat", "toe", "code"]Output["cat", "rat", "dog"] (any order)"rat" turns a corner: r in the middle, up to a, right to t. No o touches the t, so "toe" is missing, and no e touches the d, so "code" is missing too.
board = [["x"]], words = ["y"]Output[]No word is on the board, so the answer is an empty list.
1 ≤ number of rows, number of columns ≤ 12
1 ≤ len(words) ≤ 3 × 104
Each word has 1 to 10 lowercase English letters, and the words are all different.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.