Longest Common Prefix - Leetcode 14 - Python

0:00 - Read the problem
1:40 - Drawing Explanation
3:02 - Coding Explanation

leetcode 14

#prefix #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[blankomog]

I spent almost 6 hours trying to code this myself and still couldnt figure it out...lol

[OfficialRehaldinho]

Here are some optimization recommendations:
Adding to a string in Python, will always create a new string, which is not optimal.
We dont even have to store any information.
We can just return the slice up to index i (exclusive), as soon as any two characters are not equal or any index is out of bounds.

def longestCommonPrefix(self, strs: List[str]) -> str:
for i in range(len(strs[0])):
for j in range(1, len(strs)):
if i == len(strs[j]) or strs[0][i] != strs[j][i]:
return strs[j][:i]
return strs[0]

[pranit_]

it hurt me when you said "the edge cases will trip you up if you are a beginner" 😢 They made me go crazy and I have been practicing a lot!

[grub_taless]

I started out by trying to find the shortest string in the list and assigning that as prefix and then it was a disaster one after the other 😂

[elizabethr]

Such a clean and concise solution..Thanks a ton

[DmitriyKl]

This is an amazing solution - looping over the same character index of every string at once. Another solution I came up with that was intuitive to me:
1. Find the shortest string (since the prefix can't be longer than the shortest string) - O(n)
2. Set the prefix to this shortest string (in theory the entire shortest string can be the prefix)
3. compare shortest string with every other string character by character - O(n)
4. at the first character mismatch, if we haven't looped over the entire short string (prefix), update prefix to this shortened version

There are two passes, but the time complexity is still O(n)

# set prefix to first str by default
prefix = strs[0]
# prefix can't be longer than the shortest str, so we need to find it
for s in strs: # O(n)
prefix = prefix if len(prefix) < len(s) else s


for s in strs:
iP, iS = 0, 0 # index of prefix, index of current string
while iP < len(prefix) and iS < len(s): # make sure neither index is out of bounds
if prefix[iP] == s[iS]: # match? simply increment both indices
iP+=1
iS+=1
else: # first mismatch
if len(prefix[0:iP]) < len(prefix):
prefix = prefix[0:iP] # set prefix to the shorter of two
iP = len(prefix) # exit while loop

return prefix

[harunguven]

Isn't adding string to already contructed string bad practice?
What if we keep letters in list/array, than we can join them together?
Instead of s = s + new_letter,
we could do [ ... ] .append(new_letter) and finally return "".join( [ ... ] )

[watchlistsclips]

Hello neetcode could please make a video on task scheduler problem(greedy).It is in blind 75 list. It would be me a lot if you do that because i have seen many discussions and videos regarding this and couldn't understand any approach

[gmoney_swag]

i did if the length of the set of the indexed letters is equal to 1, then append that to out and keep going until there are multiple letters in the set - this beat 80 or so percent

[vaibhavmundhra]

thanks for the code i was trying to do this but wasn't able to

[commonguy]

had concept in mind. just needed a small simple how. saw your loop Nd i did it. thanks

[sangpark]

could you reiterate concept of inbound and outbound?

[dhivyashri]

hey can u do the kmp algorithm sometime, it uses the lps concept, i have tried watching sooo many tutorials for it but i've never understood, it would be great if u'd consider, thanksss

[julianrendon]

Hopefully this is a pretty straight forward solution (6 lines of code and nothing fancy):
prefix = min(strs, key=len)
strs.remove()
for s in strs:
while prefix and s.find(prefix) != 0:
prefix = prefix[:-1]
return prefix

[jeezradz]

why is it strs[0] ?
what if there is another string that is bigger ? or shorter ?

[VarunMittal-viralmutant]

How about this:

def longestCommonPrefix(self, strs: List[str]) -> str:
chars = zip(*strs)
res = ""

for c in chars:
if len(set(c)) == 1:
res += c[0]
else:
break
return res

[TheAlvaryn]

Hi what's the time & space complexities for the solution?

I believe space complexity is O(n) where n is prefix stored in string variable 'res'.
However I am unsure about time. Would it be O(n+m) where 'n' is the character size of strs[0] & 'm' is number of words in strs? Thanks.

[christmas]

I came up with a solution, but with more optimization. Let me explain:
Time complexity O(2n)
Space Complexity O(1)

1. First, we find the shortest string in the array and store it in a variable called 'ans.' We then remove this shortest string from the array.
2. Next, we iterate through all the remaining strings one by one. For each string, we check if the last character of 'ans' matches the character at the same index in the current string.
3. If there is a match, we move on to the next iteration.
4. If there is no match, we remove the character from our 'ans' variable and enter a loop. In this loop, we continue checking the second-to-last character of 'ans' and so on, until 'ans' becomes empty."

[shivanidhyani]

We can just sort the list of string first then can use the for loop it will be more easy

[jpkeys]

Aren't these two for loops nested, hence o(n^2)?