I am doing a course project where I have to build a dictionary. I have already made the dictionary using the trie. The problem now is that I have to show live suggestions as the user types the word just like on google. I cant it do the normal way like first typing the word and pressing enter. Also the delete function is not working. This is my current code so far. (I am on windows and using visual studio)
`#include<iostream>
#include<list>
#include<vector>
using namespace std;
struct node {
node* next[26];
bool end;
node()
{
for (int i = 0; i < 26; i++)
{
next[i] = nullptr;
}
end = false;
}
};
class Trie
{
private:
node* root;
void getSuggestions(node* curr, string str, list<string>& res, string curnt)
{
if (curr == nullptr) { return; }
if (curr->end == true)
{
res.push_back(curnt);
}
for (int i = 0; i < 26; i++)
{
if (curr->next[i])
{
getSuggestions(curr->next[i], str, res, curnt + char('a' + i));
}
}
}
bool removeHelper(node* curr, string str, int level, int len)
{
if (curr == nullptr) { return false; }
// Base case: If we have reached the end of the word
if (level == len)
{
if (!curr->end)
{
return false; // Word not present
}
curr->end = false; // Unset the end flag to indicate removal
// If the current node has no children, it can be deleted
if (!hasChildren(curr))
{
delete curr; // Delete the node
return true; // Node can be deleted
}
}
// Recursive case: Continue to the next level
int index = str[level] - 'a';
if (removeHelper(curr->next[index], str, level + 1, len))
{
// If the child node is marked for deletion, delete it
delete curr->next[index];
curr->next[index] = nullptr;
// Check if the current node can also be deleted
if (!hasChildren(curr) && !curr->end)
{
delete curr; // Delete the node
return true; // Node can be deleted
}
}
return false;
}
// Check if a node has any children
bool hasChildren(node* curr)
{
for (int i = 0; i < 26; i++)
{
if (curr->next[i])
{
return true;
}
}
return false;
}
public:
Trie()
{
root = new node();
}
void insert(string str)
{
node* curr = root;
for (char c : str)
{
if (!curr->next[c - 'a'])
{
curr->next[c - 'a'] = new node();
}
//cout << curr->next[c - 'a']<<" ";
curr = curr->next[c - 'a'];
}
curr->end = true;
}
void remove(string str)
{
if (str.empty())
{
cout << "Invalid input for removal";
return;
}
if (removeHelper(root, str, 0, str.length()))
{
cout << "Word removed successfully";
}
else
{
cout << "Word not found";
}
}
void suggest(string str)
{
node* curr = root;
for (char c : str)
{
if (!curr->next[c - 'a'])
{
cout << "Word not found";
return;
}
curr = curr->next[c - 'a'];
}
list<string> res;
//vector<string> res;
getSuggestions(curr, str, res, "");
cout << "-------\n";
int i = 0;
for (auto c : res)
{
cout << str << c << "\n";
i++;
if (i == 10) { return; }
}
}
void find(string str)
{
node* curr = root;
for (char c : str)
{
if (!curr->next[c - 'a'])
{
cout << "Word not found";
return;
}
curr = curr->next[c - 'a'];
}
list<string> res;
//vector<string> res;
getSuggestions(curr, str, res, "");
cout << "-------\n";
int i = 0;
for (auto c : res)
{
cout << str << c << "\n";
i++;
if (i == 1) { return; }
}
}
};
int main()
{
string str;
Trie T;
int choice = 0;
while(true)
{
cout << "\n1.Insert";
cout << "\n2.find";
cout << "\n3.suggest";
cout << "\n4.exit";
cout << "\n5.del";
cout << "\nEnter you choice: ";
cin >> choice;
if(choice==1)
{
int n;
cout << "\nEnter total number of words to insert: ";
cin >> n;
for (int i = 0; i < n; i++)
{
cout << "Insert new word\n";
cin >> str;
T.insert(str);
}
}
if(choice==2)
{
string st;
cin >> st;
T.find(st);
}
if (choice == 3)
{
string st;
cin >> st;
T.suggest(st);
}
if (choice == 4)
{
break;
}
if (choice == 5)
{
string st;
cout << "Enter word to remove \n";
cin >> st;
T.remove(st);
}
}
return 0;
}`
Aucun commentaire:
Enregistrer un commentaire