C# Trie data structure DFS algorithm practice in June 2020
June 15, 2020
Trie is a most important data structure to expedite search prefix is in the dictionary of words. I like to build a class TrieNode and also put together a Trie showcase for my past practice.
Case study
Problem statement:
Given a matrix of chars, and also a list of words as dictionry, ask to find all words in the matrix which are in given words.
Challenges:
- Build a Trie class
- Backtracking using depth first search
- Mark visited to avoid a char used twice in mutiple words
- Work on a test case to make a Trie class easy to write.
Space complexity
Use existing matrix to mark visited, backtracking if the word is not found. Extra space is not needed.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _212_word_search_II
{
class Program
{
static void Main(string[] args)
{
}
/// <summary>
/// June 15, 2020
/// class TrieNode
/// API:
/// BuildTrie
/// IsWord
/// DeDuplicate
/// </summary>
public class TrieNode
{
public TrieNode[] Next = new TrieNode[26];
public String Word { get; set; } // it is word, a string from root node to current char
/// <summary>
/// code review
/// </summary>
/// <param name="words"></param>
/// <returns></returns>
public TrieNode Build(String[] words)
{
TrieNode 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]; // iterate to next
}
// reach the leaf node of trie - add word string
trie.Word = word;
}
return root;
}
public bool IsWord()
{
return Word != null;
}
/// <summary>
/// To avoid a word to be added more than once
/// </summary>
public void DeDuplicate()
{
Word = null;
}
}
/// <summary>
/// code review on June 15, 2020
/// The idea is to start from each char in the matrix to apply depth first search, backtracking is needed to
/// reduce the space complexity, and also Trie is used to build from dictionary to make it more efficient to search
/// if the prefix is in the dictionary.
/// </summary>
/// <param name="board"></param>
/// <param name="words"></param>
/// <returns></returns>
public IList<string> FindWords(char[][] board, string[] words)
{
var set = new HashSet<string>();
var trie = new TrieNode();
var root = trie.Build(words); ;
for (int row = 0; row < board.Length; row++)
{
for (int col = 0; col < board[0].Length; col++)
{
applyDFS(board, row, col, root, set);
}
}
return set.ToList();
}
/// <summary>
/// Depth first search algorithm
/// Design concern: apply backtracking to save space - using existing matrix to mark '#' as visited
/// </summary>
/// <param name="board"></param>
/// <param name="row"></param>
/// <param name="column"></param>
/// <param name="trie"></param>
/// <param name="found"></param>
private static void applyDFS(char[][] board, int row, int column, TrieNode trie, HashSet<String> found)
{
// current char to visit
var visit = board[row][column];
// skip visited ones
if (visit == '#' || trie.Next[visit - 'a'] == null)
{
return;
}
trie = trie.Next[visit - 'a'];
if (trie.IsWord()) // the word is found, need to add to result
{
found.Add(trie.Word);
}
// mark visited
board[row][column] = '#'; // mark the node value with '#', so it will not match any char
// up, left, down, right four directions
var rows = board.Length;
var columns = board[0].Length;
if (row > 0)
{
applyDFS(board, row - 1, column, trie, found);
}
if (column > 0)
{
applyDFS(board, row, column - 1, trie, found);
}
if (row < rows - 1)
{
applyDFS(board, row + 1, column, trie, found);
}
if (column < columns - 1)
{
applyDFS(board, row, column + 1, trie, found);
}
// depth first search - backtracking
board[row][column] = visit;
}
}
}
