Trie Tree Practise – SPOJ – DICT

Hello people..! In this post we will talk about solving another competitive programming question based on trie tree. I will take up the SPOJ problem – DICT. This is a little harder than the previous trie tree practise problem, PHONELST. Now, read the problem statement carefully a couple of times. Just so that you don’t need to open SPOJ in another tab, I have posted the problem statement below –

Problem Statement
Eloy the byte is helping his son, Marcos the little one, with the homework, which consists on: Given one or more words you should search in the dictionary which word contains the proper prefix of the word given, for example set is a prefix of setter, but also of setting.
Now, neither Eloy nor Marcos wants to search the words in the dictionary (they just won’t do it)… Marcos will give you the words in the dictionary and the words to find the prefix of… You should make a program that given this, output the list of words that contains as a prefix the word given, Marcos can make mistakes sometimes, so, be careful! Marcos won’t always be telling the real prefixes all the time, in addition, sometimes Marcos can repeat the same word (while reading the dictionary), in this case, the word should be treated as it was mentioned just one time.
Input Specification
The input will consist in an integer N (1<=N<=25.000), next, N lines will follow containing a single word (maximum of 20 characters (all lowercase letters)), after that, there will be an integer K (1<=K<=22.000) containing the number of words to look in the dictionary, then, K lines containing the prefix-word.
Output Specification
The output will consist in displaying the words that are composed from the word given, you should output “Case #i:” where i is the i-th case, then, at the next line, output the list of the composed words (lexicographically-ordered), if there is none, you should output “No match.”
Sample Input
```5
set
lol
setter
setting
settings
2
set
happy
```
Sample Output
```Case #1:
setter
setting
settings
Case #2:
No match.
```

Problem in terms of Trie Tree

Firstly, we will insert the N words into a trie tree. Then, for each K prefix words –

• We will traverse the trie tree for this word.
• If it exists, we will lexicographically print the trie tree, with that node as the root. And obviously, we add the prefix to whatever we will print.
• If the word doesn’t exist at all, that is, while traversing, we would reach a dead-end (no children) node before the prefix word is fully processed, we will simply return from our traversal and print “No match.”.

So, what all do you need to solve this?

• Trie Tree insertion method.
• Trie Tree inorder traversal method (lexicographical print)

We can discard any other methods such as delete. We will need another method for searching whether a given word is present in the trie tree or not, in O(L) time, where L is the length of the word. So, take your implementation of trie tree and get it ready for solving the question by making these changes.

searchWord() Method

This is a simple trie tree traversal method, where we traverse the trie tree based on a given word. We look at each character of the word and go to the corresponding edge, in the trie tree. If there is no edge, we return null. If we have reached the end successfully, we return the node where the word ends. Try to code this procedure, you can refer to my code if you are stuck.

C++
```struct node * searchWord(struct node * TreeNode, char * word)
{
while (*word != '\0') {		// while there are alphabets to process
if (TreeNode->children[*word - CASE] != NULL) {
// there is an edge corresponding to the alphabet
TreeNode = TreeNode->children[*word - CASE];
++word;
} else {
// there is no edge corresponding to the alphabet
break;
}
}

if (*word == '\0') {
// the word was completely processed
return TreeNode;
} else {
// word is not there in trie tree
return NULL;
}
}
```

lexicographPrint() Method

This method will have very minor changes from your original method. According to our intuition, we will call this method based on the output of the searchWord method. If it is null, then it is “No match.”. If it is not null, then we begin the lexicographPrint from that node.
This method will carry an extra parameter, which will be the prefix word. Everytime we hit a leaf node, we first print the prefix word and then the remaining word traversed in this method.
Example, in the sample test case, the prefix word was “set”, so, the searchWord would return us, the location of the T node in S → E → T traversal. Then, we begin our lexicographPrint, and when we hit the end of “setter” word, we will print the “set” prefix, and the “ter” word which we gained from the lexicographPrint method.
Try to code these modifications in your code, you can refer to my code if you are stuck.

C++
```
void lexicographPrint(struct Node * trieTree, vector<char> word, char * prefix)
{
int i;
bool noChild = true;

if (trieTree->wordEnding && word.size() != 0) {
vector<char>::iterator itr = word.begin();

printf("%s", prefix);	//	print the prefix

while (itr != word.end()) {
// print the rest of the word
printf("%c", *itr);
++itr;
}

printf("\n");
}

for (i = 0; i < ALPHABETS; ++i) {
if (trieTree->children[i] != NULL) {
noChild = false;
word.push_back(CASE + i);
lexicographPrint(trieTree->children[i], word, prefix);
word.pop_back();
}
}

word.pop_back();
}
```

Putting the pieces together

Now combine your modules and prepare your main function as per the problem statement. You can refer to my code if you are stuck.

```
```

Word of Caution –

• The output in the case of a mismatch is “No match.”, not “No match”.
• The time limits are pretty tight, so your methods should be tidy.

I hope that you were able to solve this problem using a trie tree. Feel free to comment if you have any doubts. If you have any bugs in your code, I’d be glad to help, but don’t comment your entire code in the comment, please leave Ideone or PasteBin links, or if you don’t want to show your code publicly, you can fill up the response form below to mail your code to me. I will respond as soon as I can. Keep practising… Happy Coding…! 🙂