Shortest Unique prefix for every word GeeksforGeeks Full explanation of line by line code | Trie

Timestamps:
0:00 What is the problem saying?
2:50 Building Solution
9:40 Example Walkthrough
12:00 Code
Given an array of words, find all shortest unique prefixes to represent each word in the given array. Assume that no word is prefix of another.

Example 1:

Input:
N = 4
arr[] = {"zebra", "dog", "duck", "dove"}
Output: z dog du dov

Example 2:

Input:
N = 3
arr[] = {"geeksgeeks", "geeksquiz",
"geeksforgeeks"};
Output: geeksg geeksq geeksf
Explanation:

Your task:
You don't have to read input or print anything. Your task is to complete the function findPrefixes() which takes the array of strings and it's size N as input and returns a list of shortest unique prefix for each word

Expected Time Complexity: O(N*length of each word)
Expected Auxiliary Space: O(N*length of each word)

Check out our other playlists:

Dynamic Programming:

Trees:

Heaps and Maps:

Arrays and Maths:

Bit Manipulation:

Greedy Algorithms:

Sorting and Searching:

Strings:

Linked Lists:

Stack and Queues:

Two Pointers:

Graphs, BFS, DFS:

Backtracking:

Non- DSA playlists:

Probability:

SQL-Basic Join functions:

SQL-Basic Aggregate functions:

[probabilitycodingisfunis]

Time Complexity: O(N*length of each word)
Space Complexity:: O(N*length of each word)

Code in C++:

struct Trienode
{
int freq;
Trienode* child[26]; //a-z
Trienode()
{
freq = 0;
for(int i=0;i<26;i++)child[i]=NULL;
}
};

class Solution
{
public:
Trienode* root = new Trienode();
vector<string> findPrefixes(string arr[], int n)
{
//code here
vector<string>ans;
for(int i=0;i<n;i++)
buildtrie(arr[i], root);

for(int i=0;i<n;i++)
ans.push_back(buildprefix(arr[i], root));
return ans;

}

void buildtrie(string s, Trienode* root)
{
Trienode* curr = root;
for(int i=0;i<s.length();i++)
{
int index = s[i]-'a'; //25
if(curr->child[index]==NULL)
curr->child[index]= new Trienode();
curr->child[index]->freq++;
curr = curr->child[index];
}
}

string buildprefix(string s, Trienode* root)
{
Trienode* curr = root;
string ans = "";
for(int i=0;i<s.length();i++)
{
int index = s[i]-'a';
if(curr->freq==1)break;
ans+=s[i];
curr = curr->child[index];
}
return ans;
}

[Iemprashant]

Amazing explanation.
I was able to write code on my own after a great explanation.

[aravindankarthick]

Best Explanation :-) Keep rocking . Its really useful and you are teaching in a best way.

[arindamsarkar]

hi do interviewers tell to create testcases in interviews ?

[ritambanerjee]

Your explanations are great as always, but the way you write the code isn't. Writing code with proper indentation could really help, and not to mention it hurts my eyes as I kinda have OCD when it comes to code smells. But it's great! Keep up the good work.

[_Focus]

ok fine, I can't see you working so hard. You can marry me. 😁

[joshuak.n]

maam so cute yo are maam when i get optiver, i will paypal you some money maam
only because of you i will get optiver

[vanshsabuwala]

Ma'am please share your LinkedIn profile link...