Prefix and Suffix Search | Live Coding with Explanation | Leetcode - 745

[@AlgorithmsMadeEasy]

We hope you all are enjoying our videos!!! Don't forget to leave a comment!!! Please like the video to support us!!! Questions you might like: ✅✅✅[ Tree Data Structure] : kzbin.info/aero/PLJtzaiEpVo2zx-rCqLMmcFEpZw1UpGWls ✅✅✅[ Graphs Data Structure] : kzbin.info/aero/PLJtzaiEpVo2xg89cZzZCHqX03a1Vb6w7C ✅✅✅[ January 2021 Leetcoding Challenge] : kzbin.info/aero/PLJtzaiEpVo2wCalBcRcNjXQ0C6ku3dRkn ✅✅✅[ February 2021 Leetcoding Challenge] : kzbin.info/aero/PLJtzaiEpVo2wrfvII0eZQsPm-MZCmHodm ✅✅✅[ March 2021 Leetcoding Challenge] : kzbin.info/aero/PLJtzaiEpVo2zH-YC5ZiptbAvw2QZkmyk9 ✅✅✅[ April 2021 Leetcoding Challenge] :kzbin.info/aero/PLJtzaiEpVo2z9PpcJcsl5j3RXutiTU-GB ✅✅✅[ December Leetcoding Challenge] : kzbin.info/aero/PLJtzaiEpVo2xo8OdPZxrpybGR8FmzZpCA ✅✅✅[ November Leetcoding Challenge] : kzbin.info/aero/PLJtzaiEpVo2yMYz5RPH6pfB0wNnwWsK7e ✅✅✅[ August Leetcoding Challenge] : kzbin.info/aero/PLJtzaiEpVo2xu4h0gYQzvOMboclK_pZMe ✅✅✅[ July Leetcoding challenges] : kzbin.info/aero/PLJtzaiEpVo2wrUwkvexbC-vbUqVIy7qC- ✅✅✅[ June Leetcoding challenges] : kzbin.info/aero/PLJtzaiEpVo2xIPptnCvUtKrUcod2zAKG ✅✅✅[ May Leetcoding challenges] : kzbin.info/aero/PLJtzaiEpVo2wRmUCq96zsUwOVD6p66K9e ✅✅✅Cracking the Coding Interview - Unique String: kzbin.info/aero/PLJtzaiEpVo2xXf4LZb3y_BopOnLC1L4mE Struggling in a question?? Leave in a comment and we will make a video!!!🙂🙂🙂

[@aravindkumaresan2747]

Hi if you get a TLE for this solution just add a Map before inserting to the tries So that the map gets only the last string if its duplicate with the largest index because of its unique keys nature and finally sort the Lists both prefix and suffix. This approach works great

[@priyankabagal9269]

Why to sort the lists?

[@SR-we1vl]

Can you please show it implementation wise. Not able to get you!

[@sdall2000]

Thanks! That solved the TLE for me. My Kotlin init code: init { // Handle duplicate words. Save off the highest index val wordMap = mutableMapOf() words.forEachIndexed { index, word -> wordMap[word] = index } // Now we only process unique words with their highest index value wordMap.forEach { word, index -> prefixTrie.insert(word, index) suffixTrie.insert(word.reversed(), index) } }

[@rookiedrummer6838]

best explanation crystal clear and to the point no non sense gyaan

[@AlgorithmsMadeEasy]

Thankyou !!

[@hymnish_you]

Perfect Solution and Wonderful Explanation 👌

[@AlgorithmsMadeEasy]

Thanks

[@srinaths284]

@@AlgorithmsMadeEasy TLE for this solution :( we need to optimize the complexity

[@xueli5641]

Thanks for the clear and thorough explanation!

[@milenitrivedi7561]

I tried writing cpp code for the same and its giving TLE.

[@abhineshprajapati1989]

// Just use hashmap, TLE will not occur. class Trie{ public : Trie *child[26]; vector index; Trie(){ for(int i=0;ichild[ch-'a']==NULL){ temp->child[ch-'a']=new Trie(); } temp = temp->child[ch-'a']; temp->index.push_back(i); } } vector find_string(string str,Trie *root){ Trie *temp = root; for(char ch:str){ if(temp->child[ch-'a']==NULL){ return {}; } temp = temp->child[ch-'a']; } return temp->index; } class WordFilter { public: Trie *prefix,*suffix; WordFilter(vector& words) { prefix = new Trie(); suffix = new Trie(); map dic; int len = words.size(); for(int i=0;i=0;i--){ if(st.find(pre[i])!=st.end()) return pre[i]; } return -1; } };

[@suniljaiswal4415]

what if i would do like this root->index.push_back(i); root=root->child[ch]; see 11:50 in your video

[@orangeshoes]

Thanks, got it!

[@AlgorithmsMadeEasy]

Thanks

[@etarunsai5615]

could any one explain me what exactly Trie root = this , do

[@aneeshkulkarni1739]

Why was Objects.equals() used instead of Integer.compareTo() method? IMO Integer.compareTo() is more readable. Also, intValue() could be called on the elements on the index list, and == can be used since it would trigger auto-unboxing. Otherwise a great solution

[@AlgorithmsMadeEasy]

We can use both.

[@praveenj3112]

Thanks

[@RupamSasmalYt]

now this approach is giving TLE

[@kamaljosan4376]

I am getting Time limit exceeded with the above solution, any idea what changed?

[@AlgorithmsMadeEasy]

which test case?

[@kamaljosan4376]

@@AlgorithmsMadeEasy overall this solution gets TLE, does not show a specific test case.

[@surikunal2362]

Yes, I am getting TLE too. What to do.

[@pgronop]

@@surikunal2362 u should use the optimization on top of it like if the string "cat" comes three times, then store it one time only with the most latest index (or greatest index). This will make the TLE pass . The sample code looks like this Map w = new HashMap(); //Set visited = new HashSet(); for( int i=0;ia.getValue()-b.getValue()); for( int i=0;i

[@priyankabagal9269]

@@pgronop Why have you sorted l, I didnt get?

[@cicciopasticcio8469]

what about caching the previous results?

[@TechOnScreen]

Time limit exceeded for the same solution ! pls suggest.

[@TechOnScreen]

@@ashishbagul8733 yeah, m able to access. Thanks

[@AnkitGupta-44]

It gives memory limit exceed 🥺

[@srinaths284]

Yes it is TLE :(

[@muthuvalli333]

👌🏻👌🏻👌🏻

[@AlgorithmsMadeEasy]

Thanks

[@souravchakraborty9777]

TLE Solution

[@NihalSingh-ld2en]

Now, this code gives TLE...