Given an m x n board of characters and a list of string words, return all words on the board.
Each word must 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 in a word
Example 1:
This problem is most effectively done using the trie data structure. We us trie strucutre to store words then, for each character in the board, we can use backtracking to search whether we can construct a word starting from this character.
We first build a trie strucutre that stores the list of words. In every trie node, we use an array of length 26 to store possible next trie node, and a flag to indicate whether the trie node is the last letter of a word in the dictionary. We can also use a string to store the string formed by the trie nodes starting from the root node.
Suppose we have a list of words like this, words = ["oath", "pea", "eat","rain"]. The trie structure we build looks like the following. If the node is an end of a word, there is a * next to it
Next, for each character in the board, we use backtracking to search whether we can construct a word starting from this character.
In each cell of the board, we mark this call as visited, then we search the four neighboring cells. During the search, if the current cell has been visited, or does not exist in the trie, we backtrack. If we reach the end of a word in the trie, we find a solution.
This is a C++ implementation of the trie and backtracking approach:
The line thats cut off halfway finishes with:
words) {
The line thats cut off halfway finishes with:
words) {