Most Asked FAANG Coding Question! | Longest Common Prefix - Leetcode 14

dynamic programming, leetcode, coding interview question, data structures, data structures and algorithms, faang

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[calebkirschbaum]

If we are looking for just what all the items in the array have in common, why not set it to the 1st item. Then for each next item, go through the prefix checking what matches and, where it breaks.

Ex: Flower
Flow,
Flip,
Fighter,
Ferry
Gas

1st value: prefix=flower
2nd: prefix=flow
3rd:fl
4th f.
5th f
6th ""
That way you keep the scope limited without needing to check so much.

[Babas]

I love that these videos are good for a quick review for the problems we've already seen a bunch of times

[FunkyELF]

I'd go for a solution involving zip here. Any time you can avoid using "i" variables, range(), and indexing in Python is a win.

[arion]

Can we not juet set the prefix to the first String and shorten it as necessary with all other Strings? Very informally similar to constructing an intersecrion of ordered tupels

[iorvethx]

You can sort steings in array to and then check only first and last string

[TheCsTutor-qkuy]

Sort them based on lexicographical order and then compare the first with last word

[cynicap]

technically the most asked question is prohably going to be like "hi how are you, are you ready for the interview?"

[ARKGAMING]

I don't think there's a need for you to go over the array so many times.

Here's what I thought of:
create a variable to hold the value of the longest common prefix(from here on lcp) and set it to the first element of the array.
Go over all the elements, starting from index one, and set lcp to be the lcp of itself and the new element (preferably have a function for that).

And after the loop return lcp obviously.

[jameschandler]

Sort the strings in lexigraphical order using the Python built-in, then check to see if the current string of the sorred list is wholly contained by the next string. If it is increment to the next string, if not, find the index in the strings where the characters no longer equal eachoter. Then return the resulting substring. Extra credit, don't iterate through the sorted strings and only compare the first and last one.

[soumalya]

I just came here after solving this in leetcode (beating 100% in runtime and 92% in memory consumption) to check if there was a better solution. Found out I made some optimizations that he did not mention here. Optmzn 1: no need to find the length of smallest word before hand. every time you loop over a word find if the current iteration is smaller than the word size or else return the answer till that time. Optmzn 2 (small one): if you are using the 0th element as the reference why to loop over it again to check if the current character matches the reference character. Skip the 0th element entirely while matching start from pos 1

[didakad]

How can I save it if you show it so briefly?

[dithy]

Easiest done with a lcp for two words and a fold with that over the word list, since the result can be used as a new word. hs:

lcp2 (x:xs) (y:ys) | x == y = x : lcp2 xs ys
lcp2 _ _ = []

lcp = foldl1 lcp2

[PandaVlademirBerlin]

I would have used a for loop starting from the minimum length of word found in the list then slice all words using the minimum length then apply the function set to the sliced list .. if the length of the set returns 1 then that's the longest prefix

[rickyc]

There's no need to find the shortest string in the list either, we can just compare with the first string in list, which ever it is, to the rest and keep the inner loop expanding one at a time. Add a condition to return when index is out of bounds for any [1:] string because the prefix can't be bigger than any string within

[eniky]

How about creating a tree from the first word and every time when a tree gets a new branch or gets longer, cut that off and then just combine the character of the tree. End no need to find the shortest element and check what part of it is in all the others.

[Jedex]

I feel like the min_length isn't useful, you look into the whole array then count.

I'd rather have the main loop check until it finds a difference.
When the shortest word ends the last character is '\0' therefore it's different.

If all words are identical (and go out of bounds) i can set min_length to the first word or fix the condition of the loop to exit on '\0'.

This may not work in python as I'm not used to it.

Also the complexity is the same unless one word is extremely long whe you count the length.

Edit: '\0' is the string termination

[maelhostettler]

There is another version with the longest prefix shared by at least 2 words... in those more complicated cases, a prefix tree is required, too keep a decent complexity. Your solution implies that the strings are indexable data structures, otherwise, it is sub optimal.

[deepsound]

you can solve this faster with O(n) time complexity by setting the first string as the longest prefix and for every string in the list check the characters until the, dont match and save that as the longest prefix

really important because the second question after this one will be: how can you do it faster than O(n²)

[lowHPX]

What about longest common substring, how would we do that?