Problem statement:
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
For example, Given words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]Return ["eat","oath"].
Hard level algorithm
It is hard level algorithm, and Leetcode shows that there are 231.9K submissions. I like to post the algorithm for code review, I did study discussion panel on Leetcode 212 to get one idea to solve the problem, and then I carefully prepare my own learning notes as well.
It is also a good idea to discuss why Trie is needed for better time complexity.
Brute force solution is to go over each word in the dictionary, and then try to find it in the matrix. The total number of search using DFS is m (words) * rows (matrix) * columns (matrix).
The brute force solution has timeout issue through Leetcode online judge. We like to review why the time complexity should be better.
Let us go over dictionary with 4 words, "aaa", "aaaa","aaab", "aaac". If we pre-process the dictionary and store all words in a Trie, and then we do not have to go over each words to search matrix. We only need to go over each element in matrix as start char in a word, search the trie to find match words using recursive function. The number of search using DFS is rows (matrix) * columns (matrix).
Second advantage related to the above 4 words ( "aaa", "aaaa","aaab", "aaac") is taking advantage of Trie data structure. The space complexity of Trie is better compared to hashset or hashtable. The same prefix "aaa" is only repeated once in the Trie.
Trie against Hashset
Related to the test with a dictionary "aaa","aaaa","aaab","aaac","aaad", let us work together to talk about the difference.
For example, if the dictionary is saved in hashset, then go over each word in the dictionary, try to find word in matrix. For example, "aaab", the first three letters has to be compared and they are the same first, then the last letter will be checked. Same will be applied to another 4 words. In total, the prefix "aaa" will be compared exactly 5 times in order to find those 5 words.
Can we do better? Just compare the prefix "aaa" once? Cetainly we can. We can save the words in a trie instead of hashset.
a
|
a
|
a
|\ \ \
| \ \ \
| \ \ \
a b c d
Trie efficiency talk
It takes some time to get comfortable to design a Trie. So far, I have written a Trie implementation more than 4 times in C# last 3 years. Given the fact that I have worked on computer science study and full time work more than 20 years, if I practice one algorithm a day, then it is around 60,000. Definitely I should practice more how to write a trie, use the trie to get better space complexity.
How to design a Trie so that the space complexity is minimum?
For example, the dictionary has the following words, "aaa","aaaa","aaaaa","aaaaaa".
How to store them in Trie efficiently?
a
|
a
|
a word: "aaa"
|
a word: "aaaa"
|
a word: "aaaaa"
|
a word: "aaaaaa"
The above diagram shows that those four words are saved in a Trie. How many char 'a' are saved in Trie, only 6, not 3 + 4 + 5 + 6 = 18 chars. Four words are saved along the trie nodes.
Every node can represent a word, it does not have to be a leaf node.
The C# code is written based on the study of one of Leetcode discussion.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Leetcode212_AllWordsInBoard_Trie
{
/// <summary>
/// June 14, 2017
/// Leetcode 212
/// https://leetcode.com/problems/word-search-ii/#/solutions
///
/// The code is written based on the discussion of Leetcode:
/// https://discuss.leetcode.com/topic/33246/java-15ms-easiest-solution-100-00/2
///
/// </summary>
class Leetcode212_AllWordsInBoard_Trie
{
internal class TrieNode
{
public TrieNode[] Next = new TrieNode[26];
public String Word { get; set; }
/// <summary>
/// Trie is designed with 26 children, if it is the leaf node then
/// the word is added.
/// </summary>
/// <param name="words"></param>
/// <returns></returns>
public static TrieNode BuildTrie(String[] words)
{
var root = new TrieNode();
foreach (var word in words)
{
var trie = root;
foreach (var c in word.ToCharArray())
{
int current = c - 'a';
if (trie.Next[current] == null)
{
trie.Next[current] = new TrieNode();
}
trie = trie.Next[current];
}
// find node of trie to add current word
trie.Word = word;
}
return root;
}
/// <summary>
/// code review July 25, 2017
/// Understand why trie is much better on time complexity
/// every word sharing same prefix will be visited once
/// a
/// |
/// a
/// |
/// a "aaa"
/// | \ \
/// a b c "aaaa", "aaab", "aaac"
/// </summary>
public static void RunTestcaseBuildTrie()
{
string[] words = new string[] { "aaa", "aaaa", "aaab", "aaac" };
var trie = TrieNode.BuildTrie(words);
}
}
static void Main(string[] args)
{
RunTestcase();
}
public static void RunTestcase()
{
string[] words = new string[] { "oath", "pea", "eat", "rain" };
var board = new char[,]{
{'o','a','a','n'},
{'e','t','a','e'},
{'i','h','k','r'},
{'i','f','l','v'}};
var found = findWords(board, words);
}
public static List<String> findWords(char[,] board, String[] words)
{
var result = new List<string>();
var root = TrieNode.BuildTrie(words);
for (int row = 0; row < board.GetLength(0); row++)
{
for (int col = 0; col < board.GetLength(1); col++)
{
searchWordsStoredInTrie(board, root, result, row, col);
}
}
return result;
}
/// <summary>
/// Add additional note for the design:
/// function argument TrieNode trie, since trie must be updated if the word is found.
/// The word will be removed from Trie in order to avoid adding more than once.
/// The depth first search techniques used:
/// 1. mark the visit node as '#' in order to avoid looping;
/// 2. back tracking is used;
/// </summary>
/// <param name="board"></param>
/// <param name="row"></param>
/// <param name="column"></param>
/// <param name="trie"></param>
/// <param name="words"></param>
private static void searchWordsStoredInTrie(char[,] board, TrieNode trie, List<String> words, int row, int column)
{
if (row < 0 || row > (board.GetLength(0) - 1) ||
column < 0 || column > (board.GetLength(1) - 1))
{
return;
}
var visit = board[row, column];
if (visit == '#' || trie.Next[visit - 'a'] == null)
{
return;
}
trie = trie.Next[visit - 'a'];
if (trie.Word != null) // the word is found, need to add to result
{
words.Add(trie.Word);
// avoid the same word to be added more than once
// it is not a good design, update trie without telling
trie.Word = null; // deduplicate
}
// mark the node value with '#', so it will not match any char
// avoid dead loop, mark visited in depth first search
// remember this technique
board[row, column] = '#';
searchWordsStoredInTrie(board, trie, words, row - 1, column );
searchWordsStoredInTrie(board, trie, words, row, column - 1);
searchWordsStoredInTrie(board, trie, words, row + 1, column);
searchWordsStoredInTrie(board, trie, words, row, column + 1 );
board[row, column] = visit; // backtracking with DFS search
}
}
}
