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

@Hav0c1000

4 жыл бұрын

Nice explanation, btw

@techdose4u

4 жыл бұрын

No dude. Worst case is much slower. It takes O(NoOfWords * TimewithTrie). Just think it over. We are comparing all words in brute force.

@Hav0c1000

4 жыл бұрын

TECH DOSE You state the time complexity as O(n*len(smallestString)) for the first method, and O(n*len(string)) in the second method. Seems like the first one is better.

@techdose4u

4 жыл бұрын

N is no of strings. In the 1st method you have O(noOfStrings*len(string)) but in trie method...O(noOfStrings*len(string)) for building trie. After it is built, then, O(noOfWords having same prefix * len(string - prefixLength)), since we don't need to match prefix more than once. As no of queries increases, you will see the power of tri. I hope it's clear now :)

@Hav0c1000

4 жыл бұрын

@@techdose4u I see what you are saying. Thanks for taking the time to discuss!

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

@techdose4u

3 жыл бұрын

Welcome :)

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

@techdose4u

3 жыл бұрын

❤️

@bibs24

2 жыл бұрын

It has hit 100k and he deserves it.

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

@vaibhavjsr

3 жыл бұрын

when you're sorting an array of numbers, the complexity is O(nlogn) because comparing two numbers takes O(1) time [for example 2>1 takes O(1) time] But when sorting an array of strings, you'll be comparing two strings at each step. And if length of all strings is say 'm' your time complexity will become O(m*nlogn) Hence sorting might not help us out here

@mohammadosama4709

3 жыл бұрын

How that's supposed to make sense?

@chetanraghavv

Жыл бұрын

you only need minimum and maximum strings so instead of sorting, just traverse. Sorting method: m*nlogn Traversing method: m*n

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.. :)

What software do you use to explain?

Very clear explanation thank you :)

@techdose4u

4 жыл бұрын

Welcome :)

Is the Trie approach Backtracking ??

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.

@techdose4u

4 жыл бұрын

Actually trie may not seem efficient to you right now. But consider larger test cases with thousands of strings and each string being pretty long. If you keep inserting strings in a trie, huge number of strings can be accommodated in a small space. Afterwards if you wanna find longest common prefix or any specific count of strings with given prefix. It will just take O(prefix_length) TIME. In this case, bruteforce will take O(Prefix_length*NoOfStrings) TIME which is very high. So, you see TRIE is one of the best if not the best.

@treyquattro

3 жыл бұрын

@@techdose4u seems you're inventing reasoning here - finding prefixes after the fact - that wasn't part of the original problem description. This channel is very good on these kinds of problems, I just don't see an improvement over best brute force case in this instance (finding minimum length of all strings while checking first character)

@fb_a

2 жыл бұрын

@@techdose4u got it. If there is a need to persist the strings then trie is better choice to go with. Otherwise we can go with brute force.

Premiere dekha maine 🎉

GREAT teaching sir love from bangladesh

@techdose4u

4 жыл бұрын

Thanks :)

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

Thanks Bro!

@techdose4u

4 жыл бұрын

Welcome :)

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

Happy teachers day Bhaiya

lovely explanation sir

@techdose4u

3 жыл бұрын

Thanks

Good work.

@techdose4u

4 жыл бұрын

Thanks :)

Please make more on Word Break and Word boggle problem

@techdose4u

4 жыл бұрын

Okay sure.

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

@MrACrazyHobo

3 жыл бұрын

It's looking for prefix, not substring, so the answer for your example would be "".

@JatinKumar-hm7iw

3 жыл бұрын

Oh my bad... it's prefix... you are correct..!

sir this is recursive method. can you please tell the mistake. class Solution { public static String longestCommonPrefix1(String[] strs, int index) { if (index return ""; } if (index == 0) { return strs[index]; } String st = longestCommonPrefix1(strs, index - 1); StringBuffer sb = new StringBuffer(); for (int i = 0; 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); } }

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

👍

@techdose4u

3 жыл бұрын

👍

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

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