I tried implementing the code for unique prefix array using logic in video but im not getting any output plz correct the code if its wrong?
Unique Prefix Array
You are incorrectly iterating over 2D char arrays!
you may use array of strings as it is more convenient than handling char arrays.
After this make according modifications in your code!
I changed the way i was iterating in insert waala loop and the uniqueprefixarray loop but im still getting wrong output can u explain what is logical fallacy in my code ive been stuck here for a long time
insert seems fine!
In your uniquePrefixArray function return a string!
iterate over trie for given word, keep on inserting word[i] in a string(say ans) until you reach a node whose count is 1, as you reach here insert this node(whose cnt=1) as last character in your string and then return your ans string.
Try implementing this.
#include <bits/stdc++.h> using namespace std; vector result; class node { public: char data; unordered_map<char, node *> children; //bool terminal; int count; node(char d) { data = d; //terminal = false; count = 1; } }; class Trie { node *root; int cnt; public: Trie() { root = new node(’\0’); cnt = 0; } void insert(string w) { node *temp = root; for (int i = 0; i < w.length(); i++) { if (temp->children.count(w[i])) { //If node is present move to that node temp = temp->children[w[i]]; //Keeping track of frequency temp->count += 1; } else { node *n = new node(w[i]); temp->children[w[i]] = n; temp = n; } } //temp->terminal = true; } string uniquePrefixArray(string w) { node *curr = root; for (int i = 0; i < w.length(); i++) { //Keep iterating till we find variable with count=1 curr = curr->children[w[i]]; if (curr->count != 1) { continue; } else { //Inlcude substring in the vector till ith index // for (int j = 0; j <= i; j++) // { // result.push_back(w[i]); // } result.push_back(w.substr(0, i)); } } //If we have reached end of string then just push ‘-1’ in the vector result.push_back(’\0’); } // bool find(char *w) // { // node *temp = root; // for (int i = 0; w[i] != ‘\0’; i++) // { // if (temp->children.count(w[i])) // { // temp = temp->children[w[i]]; // } // else // { // return false; // } // } // //If complete word is found then terminal will be set to true // return temp->terminal; // } }; int main() { Trie t; //vector result; vector words; for (int i = 0; i < 5; i++) { string str; cin >> str; words.push_back(str); } //char words[][10] = {“Zebra”, “dog”, “dove”, “duck”, “Zebras”}; //Insert in trie for (auto it = words.begin(); it != words.end(); it++) { t.insert(*it); } // for (int i = 0; i < 5; i++) // { // t.insert(words[i]); // } for (auto it : words) { t.uniquePrefixArray(it); } // for (int i = 0; i < 5; i++) // { // t.uniquePrefixArray(result, words[i]); // } // for (int i = 0; i < result.size(); i++) // { // cout << result[i] << endl; // } for (auto it : result) { cout << it << " "; } } i have tried writing it this way its showing an error i dont understand
@aryamaan1011 please share your code on ide.codingblocks.com
also don’t worry, I just want you to reach to optimal solution by yourself, and if you can’t then I will share my approach!
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.