Here is the discussion post.
Oct. 9, 2020
745. Prefix and Suffix Search
Introduction
I started to learn how to write a Trie again. What I did is to learn ideas how to solve the problem by studing C# code using Trie, and also a short case analysis together.
Case analysis
The case is two string array, "bar","bat".
Store all the words corresponding to its prefixes and suffixes. For example, for two words bat and bar, the prefixes and suffixes dictionary will look as such:
prefixes
{
'': {'bat', 'bar'},
'b': {'bat', 'bar'},
'ba': {'bat', 'bar'},
'bar': {'bar'},
'bat': {'bat'},
}
suffixes
{
't': {'bat'},
'at': {'bat'},
'bat': {'bat'},
'r': {'bar'},
'ar': {'bar'},
'bar': {'bar'},
}
f('b', 'at') => set intersection of {'bat', 'bar'} and {'bat'} => 'bat'.
f('ba', 'r') => set intersection of {'bat', 'bar'} and {'bar'} => 'bar'.
Case study
Construct a trie using this idea, for example "bar" is the word, then construct a string "bar{bar" denoted as genius, and then start from dummy root node of Trie data structure, connect all suffix string of word concatenated by "{" + word.
dummy root node -> "bar{bar"
or-> "ar{bar"
or-> "r{bar"
The reason using '{' char since it has ascii value in decimal 123, and z's value is 122. I guess that we like to separate from suffix from prefix.
Step 1 in design:
Trie root node connects all suffix in the given word concatenated by "{" + word.
Step 2 in design:
Mark the weight for each substring along the trie
Step 3 in design:
Go through each word and assign weight using index with incremented value by one.
I will draw the diagrams to show Trie to go through test case 3, word "bat" first, and then word "bar" next, and then search using suffix "r" and prefix "ba" to find the word "bar", index value is 1.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _745_prefx_and_suffix_search
{
public class WordFilter
{
static void Main(string[] args)
{
RunTestcase3();
}
public static void RunTestcase1()
{
var filter = new WordFilter(new string[] { "bat", "bar" });
var index = filter.F("b", "at");
Debug.Assert(index == 0);
}
public static void RunTestcase2()
{
var filter = new WordFilter(new string[] { "bat", "bar" });
var index = filter.F("ba", "ar");
Debug.Assert(index == 1);
}
public static void RunTestcase3()
{
var filter = new WordFilter(new string[] { "bat", "bar" });
var index = filter.F("ba", "r");
Debug.Assert(index == 1);
}
public class TrieNode
{
public TrieNode[] Children = new TrieNode[27];
public int Weight;
public static void Insert(TrieNode root, string word, int weight)
{
string wrapped = word + "{" + word;
int end = 2 * word.Length + 1;
for (int i = 0; i <= word.Length; i++)
{
insert(root, wrapped, i, end, weight);
}
}
private static void insert(TrieNode root, string word, int start, int end, int weight)
{
TrieNode node = root;
for (int i = start; i < end; i++)
{
int index = word[i] - 'a';
if (node.Children[index] == null)
{
node.Children[index] = new TrieNode();
}
node = node.Children[index];
node.Weight = weight;
}
}
public static int Search(TrieNode root, string word)
{
TrieNode node = root;
foreach (char c in word)
{
int index = c - 'a';
if (node.Children[index] == null)
{
return -1;
}
node = node.Children[index];
}
return node.Weight;
}
}
TrieNode root;
public WordFilter(string[] words)
{
root = new TrieNode();
for (int i = 0; i < words.Length; i++)
{
TrieNode.Insert(root, words[i], i);
}
}
public int F(string prefix, string suffix)
{
TrieNode node = root;
string searchWord = suffix + "{" + prefix;
int weight = TrieNode.Search(node, searchWord);
return weight;
}
}
}
