Longest Common Prefix - Leetcode 14 - Arrays & Strings (Python)

[@GregHogg]

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

[@ethanolol3895]

such an easy explanation to follow. Love the videos!

[@GregHogg]

Glad to hear it, thank you!

[@adithyapaib]

class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: res = "" t = min(strs) j = 0 for c in t: for i in range(len(strs)): if strs[i][j] != c : return res j+=1 res+=c return res

[@kedarkulkarni9464]

At 6:25 you said you can return strs[0] instead but that is wrong for this edge case (as pointed out by leetcode) - ["ab", "a"] For above input, you get "ab" but expected is "a" (when you return strs[0] instead of s[:i])

[@mohammadrafi895]

He meant strs[0][:i] by replacing s with strs[0].

[@GregHogg]

Oh sorry thanks!

[@ThinkOutsideTheBox12345]

Thank you so much for this simple but effective solution! I spent 3 hours on the question last night and couldn’t solve myself!😅

[@GregHogg]

Hahaha no worries, glad it helped!!!

[@dimitarkiryakov6743]

@@GregHogg I did this one myself, code wasn't as clean, but I also got a solution with O(n*m). I spent an hour trying to figure out if there was something more efficient before watching the video :D

[@sonicrushXII]

There's apparently a much easier way to compare these that converts this problem into O(N). Take only the max() and min() from the array of string and perform this method on them. It genuinely works. And does so much faster

[@rishigoyal6307]

only works if it is sorted, but still would make it faster I think

[@Y2Krieger]

I think there's an issue with that logic. I think you're assuming all of the words are 'going with the flow', that they have a similar prefix pattern. But if the word list is 'flow', 'flows' 'flower' and 'horse', limiting your min and max won't evaluate that you have a word with no matching prefix.

[@sonicrushXII]

@@Y2Krieger Even still it gives you the longest common prefix. I mean I just learnt it in class

[@sonicrushXII]

Even unsorted it's still O(N)

[@dimitarkiryakov6743]

@@sonicrushXII Ok, but how would that work with the example given? shortest is "flow", longest is "flower'. That would return "flow" as prefix, but horse is in there, so it should actually be ""? Genuinely curious what we are missing

[@abhisknowledge5514]

hey greg!! just a thought like can we use set and based on its intersection we print the character?

[@mohammadrafi895]

How come you can return s[:i] at the end when s has not been declared globally?

[@mohammadrafi895]

Sorry, got it! Python makes variable of for loops available outside.

[@DuggineniChandraMouli]

@@mohammadrafi895 really?

[@mohammadrafi895]

@@DuggineniChandraMouli Yes, try it.

[@hamzapaskingakhtar]

lol same question. We come from JS I guess?

[@mbe9176]

If you have aabaaa and aacaaa then you would stop at the b/c and return aa, however if youd continue you would find aaa and return that? So you need a max length variable to compare?

[@jjkim7949]

Prefixes are at the beginning of a word, what you're suggesting is a suffix, which is at the end of a word

[@mbe9176]

@@jjkim7949 ahhh, i was thinking that its the longest subsequence present in the strings. Thanks!

[@hadizorkot2889]

The topics for this question include Trie. Would it be worth it to use tries for such a question? Time complexity to build the Trie is O(n * avg(strlen)) so technically still O(n*m) so I don't see how it could be beneficial here. Would love to know your opinion on this!

[@chanduuuuu3]

class Solution: def longestcommonprefix(self,strs): min_length= float('inf') for s in strs: if len(s)

[@hamzapaskingakhtar]

This is wrong

[@bllry2733]

why would you use ('inf') in the start of the function??

[@SergioPlaysBass]

Because when you iterate for the first time you don’t have a reference for knowing if the first element is less than something, so in the first element of the array you need to compare it to something so big that’s always bigger (infinite)

[@IamSomaMohanty]

​@@SergioPlaysBass can you please explain it with example?

[@see7529]

@@IamSomaMohanty if u set minlength=0 initially u wont get anywhere with the condition "if len(s)

[@JoeTan-nq4fq]

Is using zip function allowed? #### prefix = [] for i in map(list, zip(*strs)): if len(set(i)) != 1: return ''.join(prefix) prefix.append(i[0]) return ''.join(prefix)

[@pravuchaudhary3904]

s= input("Enter a word or any single string combination:") m=[] for i in range(len(s)): for j in range(1,len(s)+1): m.append(s[i:j]) n=[] for k in range(len(m)): if (len(m[k])>0) and len(m[k])== len(set(m[k])): n.append(m[k]) longest=0 for val in n: if len(val)>longest: longest=len(val) else: continue print("longest string=",longest)

[@wajdefadool3459]

thank you Greg

[@SrivikhilGodavarthi-y4p]

Nice one❤

[@JoeTan-nq4fq]

I use the try and except block to catch IndexError. In this case, I don't need to find the min length. ##### base = strs[0] for i in range(len(base)): # Exit if len of word is shorter than len of base try: # Exit if any char in the iteration is not the same for j in strs[1:]: if j[i] != base[i]: return j[:i] except IndexError: return j[:i] return base #####

[@siddhigolatkar8558]

Thank you

[@manoelramon8283]

there is no need to calculate the min length: if not strs: # Checking for an empty list return "" if len(strs) == 1: # If there's only one string, return it as the prefix return strs[0] for c in range(len(strs[0])): # Loop through characters of the first string for lsts in strs: if c >= len(lsts) or lsts[c] != strs[0][c]: return strs[0][:c] # Return the prefix found up to this point return strs[0] # If no differences are found, the entire first string is the prefix

[@varunpatani]

There is a better way to solve this problem this would work best if your doing your leet in python Initialize two variables first_word = sorted(strs)[0] last_word = sorted(strs)[-1] what this will do is it will sort the "strs" list in order of the characters inside of it and then we can just compare each character of the first and last word in the sorted list cause once we sort the list we wont have to worry about checking each character of each word then you can do something like this: for i in range(min(len(first_word), len(last_word))): if first_word[i] != last_word[i]: return ans ans += first_word[i] return ans remeber to initialize ans = "" (as an empty string) 😺😺😺😺

[@revel111]

I don't know how it accelerates the speed of execution in this case, but instead of appending letters using += operator, I would create a list with this letter and at the end I would do ''.join(list), since appending to the string in fact creates a new object. This principle works in java as well, by the way, so in Java you may like to use StringBuilder. Besides that your solutions in stylish asf, I like it XD

[@dimitarkiryakov6743]

Ok, but as with an above example, what if the words were 'flow', 'flows' 'flower' and 'horse'? Shortest is "flow", longest is "flower'. That would return "flow" as prefix, but "horse" is in there, so it should actually be ""?

[@eminakay1904]

we have assumed that the common prefix will be start from beggining of the word when we solving it why we do like that? common prefix can start from middle

[@Super_Shaq]

I don't think that would be a prefix, that would be a common substring. Prefixes are at the beginning of a word