Please answer in jsfiddle.net Answer must work in jsfiddle Please do not attempt
ID: 3572378 • Letter: P
Question
Please answer in jsfiddle.net Answer must work in jsfiddle Please do not attempt if you are not sure how to do it! Show it works please! Assignment 13 TRIE Spellchecker last edited by Dr. Ron Eagin 1 month ago Assignment 13 -TRIE Spellchecker Objectives Implement the TIRE Data Structure and use it to implement a complex algorithm Supports Leaning outcome 3 3. Implement data structures and algorithms in computer code. Lectures You should have gone through all the tree based structures prior to this assignment. We are now going to move into more independent research and implementation. One of the objectives is that all students can research, implement, and use a data structure, First take a look at the Wikipedia article on TRIE https:llen wikipedia.org/wikiTrie.lt is worth noting that in a TRIE each node can have more than one child node, so a TRIE is NOT a binary tree. Now let's look into what we want to be able to do with a TRIE-in this case implement a spellchecker. A spellchecker needs to determine if a word is spelled correctly, so the TRIE needs to be able to store the list of all words to check against. We must be able to add words to the TRIE, so we must implement the function; function Add ToTRIE(word) The TRIE in the Wikipedia article uses clusters of letters, but we can also model each letter as a branch in the TRIE.The example at Top Coder takes this approach https:ltwww.topcoder.com/communityldata science data-science- tutorialsMusing-tries and it may be a simpler approach for you as it more closely approximates structures that you have used (like a list). This should be enough to get you started. You wilstill need to make some decisions of how to implement the list of nodes that are in each node. Use the bulletin board to discuss The other algorithm that you need to implement wilbe to check spelling. function CheckSpelling(word) returns true or falseExplanation / Answer
Solution :
#include<stdio.h>
#include<conio.h>
struct trie
{
struct trie *end[30];
}
// Initailizes memory for trie t
trie *initializeTrie(struct trie *t) {
t=(trie *)malloc(sizeof(trie));
for(int i=0;i<;26;i++) {
t->end[i]=NULL;
}
return t;
}
// Adds a word to the existing trie
trie *addWord(struct trie *t,char *word) {
if(word[0]=='/0') {
}
else {
int i=t[0]-'a';
if(t->end[i]==NULL) {
t->end[i]=initializeTrie(t->end[i]);
}
t->end[i]=addWord(t->edges[i],++str);
}
return t;
}
// Checks whether the word's spelling is correct or not
bool spellChecker(trie *t,char *word) {
if(word[0]=='/0')
return true;
else {
int i=word[0]-'a';
if(t->end[i]!=NULL) {
spellChecker(t->end[i],++word);
}
else
return false;
}
}
// function to implement Spell Checker
int main() {
Trie *t=(trie *)malloc(sizeof(trie));
// Suppose the dictionary consists of two words
t=addWord(t,"computer");
t=addWord(t,"science");
bool check1=spellChecker(t,"computer"); // Returns true
bool check2=spellChecker(t,"computer"); // Returns false
}