typedef struct TrieNode { // number of times this string occurs in the corpus in

Question

typedef struct TrieNode
{
// number of times this string occurs in the corpus
int count;

// 26 TrieNode pointers, one for each letter of the alphabet
struct TrieNode *children[26];

// the co-occurrence subtrie for this string
struct TrieNode *subtrie;
} TrieNode;

int prefixCount(TrieNode *root, char *str); Description: Counts the number of strings in the trie (with count 2 1) that begin with the specified string, str. Note that if the specified string itself is contained within the trie, that string should be included in the count. If one of these strings occurs more than once, its entire count should be added to the return value. Note: You might find that you don't need this function to build out the text prediction functionality of your code, but you still need to implement it as part of this assignment Returns: The number of strings in the trie that begin with the specified string, str.

Explanation / Answer

Below is your code: -

// for this function make a comparison to the empty string

// if it is empty then call a function that returns the total number

// of words that exist in the trie. the function definition for that is this

int findTotalWords(TrieNode *root, int *count) {

int i;

if(root == NULL)

return 0;  

if(root->count > 1 || root->count == 1)

return *count = *count + root->count;

for(i = 0; i < 26; i++)

findTotalWords(root->children[i], count);

return *count;

}

// this fxn is called by prefixCount to get to the terminal node

// of the given string

TrieNode *findNode(TrieNode *root, char *str) {

int i, index, len = strlen(str);

if(root == NULL)

return NULL;  

for(i = 0; i < len; i++) {

// printf("%c ", str[i]);

index = tolower(str[i]) - 'a';

// printf("index: %d ", index);

if(root->children[index] == NULL)

return NULL;

root = root->children[index];

}

return root;

}

// helper fxn called by prefixCount that does all the recursive work

int prefixCountHelper(TrieNode *node, int *count) {

int i;

if(node == NULL)

return 0;

if(node->count > 1 || node->count == 1)

*count += node->count;  

for(i = 0; i < 26; i++) {

prefixCountHelper(node->children[i], count);

}

return *count;

}

// counts the number of words that contain the given prefix

int prefixCount(TrieNode *root, char *str){

int count = 0;

if(root == NULL)

return 0;

if(str == NULL)

return 0;

if(strcmp(str, "") == 0)

return count = findTotalWords(root, &count);

TrieNode *temp = findNode(root, str);

count = prefixCountHelper(temp, &count);

return count;

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.