Leetcode – 212. Word Search II

Reading Time: 4 minutes

This problem builds on Word Search, the only difference being instead of searching for one particular word, we are now given a set of words. We could take our solution from the Word Search problem and run that algorithm for every word in the data set which would result in a lot of wasted computations as the nested for loops which iterate the board looking for a matching first character will have to run for every word in the word list.

There could be a better solution using a Trie. A Trie from the word reTRIEval is a solid data structure for string matching problems. We will be using a Prefix Trie in particular.

A trie for the following dataset [oat, oath, eat, lie, lick] would look like:

Trie Data Structure

Note: The root node of a Trie always stores  null as it’s data.

The code to represent a Trie would be like:

A lot of examples online use an array to represent the children of the TrieNode. The length of the array is assumed to be the length of the alphabet that is being represented. For English, the length would be 26 assuming we stick to only upper case or lower case. If you want to mix the two then it becomes 52. In my opinion this is limiting us and we can easily get by this limitation by using a map of [Character:TrieNode]. This enables us to build a Trie with English, Chinese, Japanese, French and even with Emoji characters!

The routine to build the Trie is pretty straight forward:

We simply iterate through the list of words, extract each character from the word and add it as a child of the previous node.

Assuming the length of the biggest word is L and we have N such words in our data set, the time complexity for setting up the Trie and space complexity would be O(LN).

So how does the Trie help us? To begin with looking up if a character succeeds a character is a constant time operation in a Trie.

So how does this algorithm work? The i and j for loops in the findWords(::) function will iterate through the board and at each iteration, will check if the root of the Trie has a reference to the character at that position in the board. If yes, it will mark the current alphabet as visited and call the dfs(i: j: node: map inout: board: result inout) function starting at indices i and j. When this call returns, we updated the visited value for these indices.

The DFS algorithm used is pretty straight forward, if at any point the word field is found in a node it will be appended to the result set and then we check to see if we can go one row up, down, and one column to the left and right and then we recurse.

The code is as follows:

Time Complexity:

The time complexity of the i and j for loops is O(RC) in terms of number of rows and columns in the board. The call to perform DFS is done every time an encountered character from the board is found to be a child of the root Trie node and DFS is recursively called based on the length of the word and if we have N words of size L, the recursion will take O(LN). It really comes down to a situation if RC >> LN then O(RC) is the dominating factor and vice versa.

Space Complexity:

There’s O(LN) additional space needed for setting up the Trie.

Problem taken from Leetcode.

Solution hosted on Github.

 

 

Mohit AthwaniLeetcode – 212. Word Search II

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.