L3. Longest Word With All Prefixes | Complete String | Trie

In case you are thinking to buy courses, please check below:

In this video, we discuss the question longest word with all prefixes!

Please share this channel as much as you can. Also, it's an earnest request to drop a comment "understood" if you are watching this video, so that I get to know you understood from this video.

-------------------------------------------------------------------------------------------------------------

[takeUforward]

Lets start a new trend, please comment "understood" in case you did :)

[manikantsharma]

Small correction in calling the function checkIfPrefixExists :
It should be trie.checkIfPrefixExists(it) //Not just checkIfPrefixExists(it)
And Thank U Striver for taking us forward!

[bidiptoroy]

Understood, Thanks a lot.

Implemented it on my own and this is how I did it:
I used the search function of trie, and instead of traversing through nodes, and I checked for the string only if it is larger than the previous largest one, another thing is that in Java I stings are immutable, so I stored the index of the largest string instead of the largest string itself.

[ManishKumar-kwqe]

I don't how i come up to this approach but it is working
USED RECURSION
TC -(n * m^2) n for the main for loop and m for the rec and m for the .find();
you can use the unordered set the TC -O(n*m);

sc-O(n) + m -->n for the set and m for the recursion stack space

bool rec(int idx, string str, set<string>& st, string word) {
if (idx >= word.size()) {
return true; // Base case: all characters have been processed
}

str += word[idx];

if (st.find(str) == st.end()) {
return false; // If prefix not found, return false
}

return rec(idx + 1, str, st, word);
}

string completeString(int n, vector<string>& a) {
set<string> st(a.begin(), a.end());
string valid = "";

for (int i = 0; i < a.size(); i++) {
string str="";
if (rec(0, str, st, a[i])) {
// Update valid string based on size and lexicographical order
if (a[i].size() > valid.size()) {
valid = a[i];
} else if (a[i].size() == valid.size() && a[i] < valid) { lexicographical
valid = a[i];
}
}
}

return valid.length() > 0 ? valid : "None";
}

[harshitsoni]

In function isPrefix, we dont need to check if the word exists in the trie we just need to ensure that every node has flag value true because we are not asked to search for a new word.

[chandrachurmukherjeejucse]

Understood and did it myself before watching this. All thanks to striver. ❤

[kunalaggarwal]

Another solution for this question using maps:-

string completeString(int n, vector<string> &a){
sort(a.begin(), a.end());
string ans = "";
unordered_map<string, int>m;
m[""]++;
int count = 0;
for(auto i : a){
string temp = i.substr(0, i.size()-1);
if(m[temp]!=0){
if(ans.size()<i.size())
ans = i;
m[i]++;
}
}
return ans=="" ? "None" : ans;
}

[rishabhkumar]

string striver_Best_Explanation = "Understood";

[alok]

Bhaiya bahaut badhiya samjhaye hain aap. Thanks 👍🙌

[Ratansingh]

Just a question, while iterating each input in completeString function

Why don't you simply skip it if it's length is lower than current answer candidate. Why to even check if prefix exists or not.

[tanmaybro]

as the constraints are 1 <= N <= 10^5
1 <= A[i].length <= 10^5.
How O(n*L(MAX)) works?

[priyanshkumar]

understood!! Great Problem & explanation. Thanks:)))!!!

[iampatelajeet]

Understood everything, thanks bhaiya.

[mount]

bhaiya has further made the code more readible, follow the link in the description

[girishbhargava]

Understood
Please make a video on the topic, "WHAT TYPE OF QUESTIONS ARE ASKED IN INTERSHIP ROUNDS OF BIG COMPANIES"
And how should we prepare from them...

[Anonymous-ujjx]

Hello Striver! Thanks for all your videos.
I don't think we have to write another function to check prefixes, we can check while inserting if already sort the strings by length, even it reduces complexity by a greater amount.

My implementation of the idea, which passed all cases in code studio also:

struct Node{
    vector<Node*> children;
    bool isEnd;
    Node(){
        children.assign(26, NULL);
        isEnd = false;
    }
   
    bool containsKey(char ch){
        return children[ch - 'a']!=NULL;
    }
   
    void put(char ch, Node* node){
        children[ch - 'a'] = node;
    }
   
    Node* get(char ch){
        return children[ch - 'a'];
    }
};

class Trie{
private:
    Node* root;
public:
    Trie(){
        root = new Node();
    }
   
    bool insertAndCheck(string word){
        Node* node = root;
        for(int i=0; i<word.length()-1; i++){
            if(node->containsKey(word[i]) && node->isEnd){
                node = node->get(word[i]);
            } else {
                return false;
            }
        }
        node->put(word[word.length()-1], new Node());
        node->isEnd = true;
        return true;
    }
     
};

string completeString(int n, vector<string> &a){
    sort(a.begin(), a.end(), [](string x, string y){return x.length() < y.length();});
    string longest = "";
    Trie obj;
    for(string word : a){
        if(obj.insertAndCheck(word)){
            if(word.length() > longest.length()){
                longest = word;
            } else if(word.length() == longest.length() && word < longest){
                longest = word;
            }
        }
    }
   
    return (longest == "" ? "None" : longest);
}

[tangyao]

time complexity should be: O(n* it.length() * sub.string.length())
n= for traversing the array
it.length()= for all substring of a[i]
substing.length()= when we are checking it in trie is it existing or not ?

little confusion😥😥

[kushagrasrivastava]

This is not optimal, since we are checking for each prefix from start, doing dfs would work fine.

[AbhishekVerma-zcem]

understood "Awesome Playlist"

[tech_wizard]

Is your graph n trees series enough to crack tech interviews of tech giant's (for DSA beginners)