Trie method is slower in the worst case vs Brute Force, and uses O(n) space... why use the trie then?

Thank you, your videos help me to understand problems very quickly. It's precise and crisp.

One day this channel is gonna hit 100k subs and then I will be bragging about how helpful u were!!

The trie problem can be solved in this manner also: We look for the smallest word in the input array and then form a trie with that word only... Suppose the words are apple ape and apps.. Then we form a trie with ape only a(wc = 1), p(wc = 1) , e(wc = 1)..then we check for others words.. For apple we check a (wc = 2) p( wc = 2 ) and then as e and p are not matching we stop there and go for the next word apps a(wc = 3) p(wc = 3) and then we finally stop.. Then we traverse from the root to extract the longest common prefix (upto that node whose wc = length of input array) Correct me if i am wrong.. :)

Very clear explanation thank you :)

GREAT teaching sir love from bangladesh

Even though this takes a bit more time we can move further to O(nlogn) efficiency After sorting the string array -O(nlogn) We can check the first string and last string of the array -O(n) O(nlogn) + O(n) Might reduce complexity a lot space as well as time

Premiere dekha maine 🎉

method 1 which is kind of a brute force method but I like this method 😂 I love that method

What software do you use to explain?

lovely explanation sir

The Brute force method 1 is kinda better I think. It does screening of each and every element and break accordingly. Consider the following input of strings to compare: ["Carbonate", "Carosal", "Car"]. If we use method 1 we will break out immediately after "Car" words length is reached. Whereas if we use trie we will be iterating through the entire 1st word, entire 2nd word and then entire 3rd word. Using 1 method, We traverse through only 1st three characters of all the strings and then break out . By the way is there any other algorithm to solve string comparisons. I am hunting algorithms for this problem.

Is the Trie approach Backtracking ??

Good work.

Thanks Bro!

Happy teachers day Bhaiya

Apparently, you don't need to maintain any counters. We just traverse until each node has children of size 1.

Please make more on Word Break and Word boggle problem

this code is much better then your first method code as both of them are o(n^2) tc and o(1) sc class Solution { public: string longestCommonPrefix(vector& strs) { //TC - O(N ^ 2) // SC - O(1) string ans = ""; for(int i=0;i

sir this is recursive method. can you please tell the mistake. class Solution { public static String longestCommonPrefix1(String[] strs, int index) { if (index < 0) { return ""; } if (index == 0) { return strs[index]; } String st = longestCommonPrefix1(strs, index - 1); StringBuffer sb = new StringBuffer(); for (int i = 0; i < Math.min(st.length(), strs[strs.length-1].length()); i++) { if (st.charAt(i) == strs[strs.length - 1].charAt(i)) { sb.append(st.charAt(i)); } else { return sb.toString(); } } return sb.toString(); } public static String longestCommonPrefix(String[] strs) { return longestCommonPrefix1(strs, strs.length - 1); } }

👍

class Solution { public: string longestCommonPrefix(vector& strs) { int i=0,j=0,count=0,min=INT_MAX; string s; while(i

can anyone pls tell me how first method is applicable to apple, mapple , creamapple ??

yeah this one makes no sense. The trie version is much more inefficient in terms of space - brute force requires no extra space - and in the best case scenario is the same time complexity as brute force - number of strings * length of shortest prefix when shortest prefix is the length of the shortest string