Code to implement a command-line search auto complete interface won't work, whats the problem? #include #include #include #include const int ALPHABET_SIZE = 28; class Trie { private: structTrieNode { //Node struct which contains a a child node for each letter of the alphabet TrieNode *children[ALPHABET_SIZE]; boolisEndOfWord;//bool to determine if letter is the last in a word TrieNode() {//constructor to initially set every child node to empty, and bool to false for (int i = 0; i < ALPHABET_SIZE; i++) { children[i] = NULL; } isEndOfWord = false; } ~TrieNode() {//deconstructor for (int i = 0; i < ALPHABET_SIZE; i++) { if (children[i] != NULL) { deletechildren[i]; } } } }; TrieNode *root;//pointer to point to first letter in word public: Trie() { root = newTrieNode(); //new node is created for first letter inserted } ~Trie() { deleteroot; } //this function inserts every word in the dictionary to the trie to create a path from first letter to last letter. //make root=first letter, see if the next letter exists as a child of root, if it doesnt create it, and move current to the next letter in word voidinsert(const std::string &word) { TrieNode *current = root;//pointer to point to current letter, which begins at root node(bc its the first letter) for (char c : word) { int index; if(c=='_'){ index = ALPHABET_SIZE - 1; } else{ index = c - 'a'; } if (current->children[index] == NULL) {//check if the next letter in the word currently exists as a child of the current node current->children[index] = new TrieNode();//if it doesnt create a new node and assign it to the child(next letter) } current = current->children[index];//make current the node it was pointing to(next letter). now the current node is the next letter } current->isEndOfWord = true;//after looping through each letter, current points to last letter so change its bool to true } boolsearch(const std::string &word) { TrieNode *current = root; for (char c : word) { int index; if(c=='_'){ index=ALPHABET_SIZE -1; } else{ index=c-'a'; } if (current->children[index] == NULL) { returnfalse;//if the next letter isnt a child of current node, return false akatheres no more searching to be done } current = current->children[index]; } return current->isEndOfWord;//if we get all the way through the search word without returning false, signal the last letter as the end of the word. } std::vector autocomplete(const std::string &prefix) { std::vector results; TrieNode *current = root; //the user input will be stored in prefix. //traverse the tree to see if each letter in prefix lines with with a word //functions similarly to search function but traverses user input instead of dictionary word and doesnt alter the isendofwordbool for (char c : prefix) { int index; if(c=='_'){ index=ALPHABET_SIZE-1; } else{ index=c-'a'; } if (current->children[index] == NULL) { return results; } current = current->children[index]; } //if we makeit through the loop that means there is a path in tree the aligns with user input prefix. //current will now be pointing to the last letter in the prefix dfs(current, prefix, results); return results; } private: //function for depth first search. //from the starting letter, it looks at input, checks if the full input is a word voiddfs(TrieNode *node, const std::string &prefix, std::vector &results) { if (node->isEndOfWord) { results.push_back(prefix);//checks if full prefix input is a word, and if it is adds it to the result vector } for (int i = 0; i < ALPHABET_SIZE; i++) { if (node->children[i] != NULL) {//for each letter in alphabet check if the current node has that letter as a child char c = i + 'a';//if it does exist, assign that letter to char c, add it to the prefix, and redo the traversal dfs(node->children[i], prefix + c, results); } } } }; int main() { Trie trie; std::ifstream file("Dictionary.txt"); if (file.is_open()) { std::string word; while (file >> word) { trie.insert(word); } file.close(); } std::cout << "Type your search:\n"; std::string query; while (std::getline(std::cin, query)) { std::vector options = trie.autocomplete(query); std::cout << "Possible searches include: "; for (int i = 0; i < options.size(); i++) { std::cout << options[i]; if (i != options.size() - 1) { std::cout << ", "; } } std::cout << '\n'; std::cout << "Please type your search: \n"; } return 0; }
Code to implement a command-line search auto complete interface won't work, whats the problem?
#include <iostream>
#include <fstream>
#include <string>
#include <
const int ALPHABET_SIZE = 28;
class Trie {
private:
structTrieNode { //Node struct which contains a a child node for each letter of the alphabet
TrieNode *children[ALPHABET_SIZE];
boolisEndOfWord;//bool to determine if letter is the last in a word
TrieNode() {//constructor to initially set every child node to empty, and bool to false
for (int i = 0; i < ALPHABET_SIZE; i++) {
children[i] = NULL;
}
isEndOfWord = false;
}
~TrieNode() {//deconstructor
for (int i = 0; i < ALPHABET_SIZE; i++) {
if (children[i] != NULL) {
deletechildren[i];
}
}
}
};
TrieNode *root;//pointer to point to first letter in word
public:
Trie() {
root = newTrieNode(); //new node is created for first letter inserted
}
~Trie() {
deleteroot;
}
//this function inserts every word in the dictionary to the trie to create a path from first letter to last letter.
//make root=first letter, see if the next letter exists as a child of root, if it doesnt create it, and move current to the next letter in word
voidinsert(const std::string &word) {
TrieNode *current = root;//pointer to point to current letter, which begins at root node(bc its the first letter)
for (char c : word) {
int index;
if(c=='_'){
index = ALPHABET_SIZE - 1;
}
else{
index = c - 'a';
}
if (current->children[index] == NULL) {//check if the next letter in the word currently exists as a child of the current node
current->children[index] = new TrieNode();//if it doesnt create a new node and assign it to the child(next letter)
}
current = current->children[index];//make current the node it was pointing to(next letter). now the current node is the next letter
}
current->isEndOfWord = true;//after looping through each letter, current points to last letter so change its bool to true
}
boolsearch(const std::string &word) {
TrieNode *current = root;
for (char c : word) {
int index;
if(c=='_'){
index=ALPHABET_SIZE -1;
}
else{
index=c-'a';
}
if (current->children[index] == NULL) {
returnfalse;//if the next letter isnt a child of current node, return false akatheres no more searching to be done
}
current = current->children[index];
}
return current->isEndOfWord;//if we get all the way through the search word without returning false, signal the last letter as the end of the word.
}
std::vector<std::string> autocomplete(const std::string &prefix) {
std::vector<std::string> results;
TrieNode *current = root;
//the user input will be stored in prefix.
//traverse the tree to see if each letter in prefix lines with with a word
//functions similarly to search function but traverses user input instead of dictionary word and doesnt alter the isendofwordbool
for (char c : prefix) {
int index;
if(c=='_'){
index=ALPHABET_SIZE-1;
}
else{
index=c-'a';
}
if (current->children[index] == NULL) {
return results;
}
current = current->children[index];
}
//if we makeit through the loop that means there is a path in tree the aligns with user input prefix.
//current will now be pointing to the last letter in the prefix
dfs(current, prefix, results);
return results;
}
private:
//function for depth first search.
//from the starting letter, it looks at input, checks if the full input is a word
voiddfs(TrieNode *node, const std::string &prefix, std::vector<std::string> &results) {
if (node->isEndOfWord) {
results.push_back(prefix);//checks if full prefix input is a word, and if it is adds it to the result vector
}
for (int i = 0; i < ALPHABET_SIZE; i++) {
if (node->children[i] != NULL) {//for each letter in alphabet check if the current node has that letter as a child
char c = i + 'a';//if it does exist, assign that letter to char c, add it to the prefix, and redo the traversal
dfs(node->children[i], prefix + c, results);
}
}
}
};
int main() {
Trie trie;
std::ifstream file("Dictionary.txt");
if (file.is_open()) {
std::string word;
while (file >> word) {
trie.insert(word);
}
file.close();
}
std::cout << "Type your search:\n";
std::string query;
while (std::getline(std::cin, query)) {
std::vector<std::string> options = trie.autocomplete(query);
std::cout << "Possible searches include: ";
for (int i = 0; i < options.size(); i++) {
std::cout << options[i];
if (i != options.size() - 1) {
std::cout << ", ";
}
}
std::cout << '\n';
std::cout << "Please type your search: \n";
}
return 0;
}
![79
81
03
83
84
85
88
90
890
00
90
20
910
02
92
02
93
04
940
05
95
06
07
97
09
98
09
99
100
101
101
107
107
108
100
102
103
104
105
106
100 1
1
109
105
110
110
111
11
112
114
115
119
116
0 0
1176
118
110
119
119
1200
120
1210
122
122
123
125
124
131
132
122
133
BA
134
125
135
126
136
127
137
120
138
120
139
158
140
141
1
142
142
143
20
144
ME
145
145
146
190
147-
20
148
270
149
150
150
454
151
224
152
1
-}¶
152
153 1
TEA
154
155 1
156
157 }¶
158
std::vector<std::string> autocomplete(const std::string &prefix). {1
std::vector<std::string> results;
TrieNode. *current
root;
.//the. user input will be stored in prefix.
-}
return current->is EndOfWord;//if we get all the way through the search word without returning false, signal the last letter as the end of the word.
·}
125
125
126
20
}¶
127
};¶
150
128 int main() {
129
130 1
LUNICITE - CUTTUITE CHE CUT CINTA
//traverse the tree to see if each letter in prefix lines with with a word
.//functions. similarly to search function but traverses user input instead of dictionary word and doesnt alter the isendofword bool
for (char c: prefix) {
·}¶
·}
private:
...//function for depth first search.
.//from the starting letter, it looks at input, checks if the full input is a word
·}¶
.... Trie trie;
int index;1
if (c=='_') {1
index=ALPHABET_SIZE-1; 1
void dfs (TrieNode *node, const std::string &prefix, std::vector<std::string> &results). {1
if (node->is EndOfWord) {1
results.push_back(prefix);//checks if full prefix input is a word, and if it is adds it to the result vector
}¶
}¶
else{
index=c-'a';
}1
//if we make it through the loop that means there is a path in tree the aligns with user input.prefix.
//current will now be pointing to the last letter in the prefix
dfs (current, prefix, results); 1
return results;
}¶
if (current->children [index] == NULL) {
.....return results;
for (int i = 0; i < ALPHABET_SIZE; i++) {1
if (node->children [i] != NULL) {//for each letter in alphabet check if the current node has that letter as a child
char c= i + 'a';//if it does exist, assign that letter to char c, add it to the prefix, and redo the traversal
dfs (node->children [i], prefix + c, results);
}¶
current = current->children [index];
std::ifstream file("Dictionary.txt");"
if (file.is_open()) {1
std::string word;
while (file >> word) {1
trie.insert (word);
return 0;1
file.close();1
std::cout << "Type your search: \n";
std::string query;
while (std::getline(std::cin, query)). {1
std::vector<std::string> options = trie.autocomplete (query);
std::cout << "Possible searches include: ";
for (int i = 0; i < options.size(); i++) {1
std::cout << options [i];1
if (i = options.size()-1) {
std::cout <<",";¶
-}¶
}¶
std::cout << '\n';
std::cout << "Please type your search: \n";](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fcb3b4814-c631-486e-b868-46cfd98a6eb6%2Fc21087fa-0143-49cc-bed8-609e287077b4%2Fzvmxxk_processed.png&w=3840&q=75)
![3
10→
11
14
15Ⓒ
16
18
30
ដងននននជនទាំផងនគំតនខ្ន
22
25
26
36
37→
38
39
40
41
12
42
75
43
77
44-
AE
45
46
000
47
48-
49
53
56
57
58
59
60
33 Trie () {1
01
61
62
02
63-
29
64
65-
22
66
67-
07
68
69
09
70
71
44
72
44
73
P
74-
75
+2
76
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
77
!!
78
79
80
81
820
const int ALPHABET_SIZE = 28; 1
class Trie. {1
private:
struct TrieNode { //Node struct which contains a a child. node for each letter of the alphabet
TrieNode. *children [ALPHABET_SIZE];
bool is EndOfWord;//bool to determine if letter is the last in a word
-};¶
public:
TrieNode() {//constructor to initially set every child node to empty, and bool. to false
for (int i = 0; i < ALPHABET_SIZE; i++) {
children[i] = NULL;
...
·}¶
is EndOfWord = false;
~TrieNode() {//deconstructor
}1
....TrieNode. *root;//pointer to point to first letter in word
}¶
for (int i = 0; i < ALPHABET_SIZE; i++) {¶
if (children [i] != NULL) {1
delete children [i];
-}¶
-}¶
...root = new TrieNode(); //new node is created for first letter. inserted
¶
~Trie() {1
}¶
delete root;
//this function inserts every word in the dictionary to the trie to create a path from first letter to last. letter.
//make root=first letter, see if the next letter exists as a child of root, if it doesnt create it, and move current to the next letter in word
void insert(const std::string &word) {1
TrieNode *current = root;//pointer to point to current letter, which begins at root node (bc its the first letter)
for (char c: word) {
int index;
if (c==''){
}
else{
index = ALPHABET_SIZE - 1;1
index = c 'a';
}1
if (current->children [index] == NULL) {//check if the next letter in the word currently exists as a child of the current.node
current->children [index] = new TrieNode();//if it doesnt create a new node and assign it to the child (next letter) 1
}
current = current->children [index];//make current the node it was pointing to (next letter). now the current node is the next letter
current->isEndOfWord = true; //after looping through each letter, current points to last letter so change its bool. to. true
}¶
bool search(const std::string &word) {1
TrieNode. *current
for (char c: word) {1
int index;
if (c==''){1
root; 1
2 index=ALPHABET_SIZE -1; 1
}
else{
index=c-'a'; 1
}1
if (current->children [index] == NULL). {1
}1
return false;//if the next letter isnt a child of current node, return false aka theres no more searching to be done
current = current->children [index];
return current->is EndOfWord;//if we get all the way through the search word without returning false, signal the last letter as the end of the word.
vector<std::strings, autocompletelconst.std..string. Sprefix). Sa](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fcb3b4814-c631-486e-b868-46cfd98a6eb6%2Fc21087fa-0143-49cc-bed8-609e287077b4%2F5bqu9ag_processed.png&w=3840&q=75)
Step by step
Solved in 3 steps with 1 images
