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

Please check my playlists for free DSA problem solutions:

My Favorite Courses:

Data Structures & Algorithms:

Python:

Web Dev / Full Stack:

Cloud Development:

Game Development:

SQL & Data Science:

Machine Learning & AI:

[GregHogg]

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

[chanduuuuu]

class Solution:
def longestcommonprefix(self, strs):

min_length= float('inf')
for s in strs:
if len(s)<min_length:
min_length=len(s)

i=0
while i<min_length:
char = strs[0][i]
for s in strs:
if s[i]!=char:
return strs[0][:i]
return strs[0][:min_length]

s1 = Solution()
print(s1.longestcommonprefix(["flower", "flow", "flows"]))

[ThinkOutsideTheBox]

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

[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

[ethanolol]

such an easy explanation to follow. Love the videos!

[kedarkulkarni]

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])

[pravuchaudhary]

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)

[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)

😺😺😺😺

[hadizorkot]

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!

[abhisknowledge]

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

[JoeTan-nqfq]

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)

[JoeTan-nqfq]

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

[mohammadrafi]

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

[mbe]

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?

[manoelramon]

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

[bllry]

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

[eminakay]

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