// Helper method for completion_count). Here\'sa (recursive) algorithm Base case
ID: 3720161 • Letter: #
Question
// Helper method for completion_count). Here'sa (recursive) algorithm Base case: If root is nullptr, then return e Recursive case -Return the sum of the completion counts of the left and right subtrees plus if root->s does not start with x. 1 if root->s does start with x. Fint Autocompleter::completion_count_recurse(string x,Node* root) E// Helper method for completions() Here'sa (recursive) algorithm Base case: I If root is nullptr, return. f If the last entry of the suggestions array is not, return I (since completions() has already found 5 suggestions) Recursive case -Recurse on left subtree If root->s starts with x, add root->s to first empty location in suggestions -Recurse on right subtree. Evoid Autocompleter::completions_recurse(string x, string suggestions, Node root)Explanation / Answer
Not very sure which language these programs are in but based on the function signatures, I am answering this question in C++ .
The first helper function needs to return the recursive counts, else return if the root is nullptr
int AutoCompleter::completion_count_recurse(string x, Node* root){
if(root == nullptr)
return;
if(startsWith(root->s,x)){
return 1+completion_count_recurse(x,root->left) + completion_count_recurse(x,root->right);
}
else{
return completion_count_recurse(x,root->left) + completion_count_recurse(x,root->right);
}
}
bool startsWith(std::string mainStr, std::string toMatch)
{
// std::string::find returns 0 if toMatch is found at starting
if(mainStr.find(toMatch) == 0)
return true;
else
return false;
}
The second recusrive function is for completion with a conditions string array :
void Autocompleter::completions_recurse(string x, string* suggestions, Node* root){
if(root == nullptr)
return;
int myStrArrLen = sizeof(suggestions)/sizeof(suggestions[0]);
string lastObj = "**";
if(s[myStrArrLen - 1].compare(lastObj) == 0)
return;
completions_recurse( x, suggestions, root->left);
if(startsWith(root->s,x)){
int i=0;
while(i<myStrArrLen){
if(suggestions[i].empty()){
suggestions[i] = root->s;
break;
}
}
completions_recurse( x, suggestions, root->right);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.