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]
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
nice optimization.... yet the time complexity is not O(n) it is O(n*m) where n is the number of strings in the array and the m is the average length of the shortest string (found in the first loop O(n)))
I started by assigning the first element of the array strs to the prefix and then deleting the characters that didn't match. turns out loop through a changing element is not a good idea, also in rust the delete character thing is a O(n) operation lol.
You can totally do it that way! That's how I did it: class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: shortest = min(strs, key=len) for i, char in enumerate(shortest): if any(s[i] != char for s in strs): return shortest[:i] return shortest 1. First we find the shortest string 2. Then for every string s we make sure that shortest[i] == s[i]. I use any() but a for-loop also works 3. If we don't match all characters we return shortest[:i] which is just whatever we matched so far. For example if characters 0 and 1 matched but it failed for i=2, then we return shortest[:2]. 4. If we match all characters in shortest then obviously the longest common prefix is just shortest, so return that. It takes one extra pass over the array to get the shortest string, but it doesn't change the time complexity. And it removes the edge case of checking if i goes past the length of any string.
@@davide816 min_length = min(len(s) for s in strs) common = "" for i in range(min_length): for j in range(len(strs) - 1): if strs[j][i] != strs[-1][i]: return common common += strs[-1][i] return common I did it this way. Not selecting the shortest string but selecting the length of it.
Approached it the same way. Broke my head a few times but I somehow arrived at a solution 😭 class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: result = "" count = 0 strMin = min(strs, key=len) for i in range(len(strMin)): for j in range(len(strs)): if strMin[i] != strs[j][i]: return result else: count += 1 if count == len(strs): result += strMin[i] count = 0 return result
I've been using Python for about 10 years, used it for so many projects and still struggle with these tasks. It's like I have a mental block to even understanding how to start and do these.
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( [ ... ] )
@@ekcelhenrichekoumelong4457 strings are immutable in python so when you append to a string, youre creating a new string which is O(n) since you have to copy the characters of the original string to the new string
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
would it be more efficient to sort the list and compare the first and the last element in the sorted list, instead of comparing every single element to the s[0]? sorting would be O(n logn) and comparing the first and the last element would be O(n), i believe. idk if I'm missing somethign. class Solution(object): def longestCommonPrefix(self, strs): sorted_strs = sorted(strs) res = '' i = 0 f_str = sorted_strs[0] l_str = sorted_strs[-1] while i < len(f_str) and i < len(l_str): if f_str[i] == l_str[i]: res += f_str[i] i+=1 else: return res return res
No, it has worse time complexity because you're sorting which is O(N log N). Conceptually your idea works fine though. But instead of sorting, you can use min and max in O(N) time. shortest = min(strs) longest = max(strs) That'll make it roughly an optimal solution.
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
@@thenerdycoder07 zip(*strs) will collect all the corresponding characters from each of the given string. Number of elements in the list is the length of shortest string Eg: chars = zip('flower', 'flow', 'flight') chars = [(f, f, f), (l, l, l), (o, o, i), (w, w, g)] Then we are just iterating this chars list and checking if all elements are same: len(set(char)) == 1 If it is, we add char to res else break as soon as we find the first mismatch
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: ''' Use the first string as the basis. Compare each string, increment i when characters match, and update the basis. ''' # Use the first string as the basis basis = strs[0] # Iterate over each string for s in strs: i = 0 # Increment i as long as characters match while i < len(basis) and i < len(s) and s[i] == basis[i]: i += 1 basis = s[:i] # Update the basis (it will get shorter) return basis
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: basis = strs[0] for s in strs: i = 0 while i < len(basis) and i < len(s) and s[i] == basis[i]: i += 1 basis = s[:i] # Update the basis return basis
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
@@dhivyashri6554 yes , I recently watched the video and understood it , but I don't think I will be able to code It yet are you preparing for your coding interview
I had the same problem and had to watch multiple different videos and read multiple articles to get it to actually make sense. I think this video was the most informative though. ruclips.net/video/GTJr8OvyEVQ/видео.html&ab_channel=TusharRoy-CodingMadeSimple
x = ["flower", "flosing", "flowing"] prefix = "" for i in range(len(x[0])): flag = 0 temp = x[0][i] for j in range(1, len(x)): if not x[j][i] == temp: flag = 0 break else: flag = 1 if flag ==1: prefix+=temp else: pass print(prefix)
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
If anyone confused by why he puts range(len(strs[0])) instead of the length of the shortest string, you can change your code to this one below so it fits the logic we'll iterate through the shortest string #Find shortest string length n = min(strs,key=len) res = "" for i in range(len(n)): for char in strs: if char[i] != strs[0][i]: return res res += strs[0][i] return res
Shouldn't that be n[i] within the if condition n = min(strs,key=len) ## shortest string res = "" for i in range(len(n)): for char in strs: if char[i] != n[i]: ## check if condition with the shortest string return res res += n[i] return res
U a God- My implementation with a Trie in Python: class TrieNode: def __init__(self): self.child = {} self.count = 1 class Solution(object): def __init__(self): self.root = TrieNode() def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ for word in strs: self.insert(word) # create the Trie total_strs = len(strs) # {'fl': 3} ans = [] word = strs[0] # use to find the common prefix in the Trie curr = self.root for ch in word: if ch in curr.child and curr.child[ch].count == total_strs: ans.append(ch) curr = curr.child[ch] else: break # no common prefix among the input strings return "".join(ans)
def insert(self, word): curr = self.root for ch in word: if ch not in curr.child: curr.child[ch] = TrieNode() else: curr.child[ch].count += 1 curr = curr.child[ch]
res='' for i in range(0,len(strs[0])): for s in range(len(strs)): if i==len(strs[s]) or strs[s][i]!= strs[0][i]: return res res= res+strs[s][i] return res This code looks more readable and understandable
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."
Are you certain about the matching in step 2-4? I think if you iterate through string 1 by 1, it takes O(n). Then the index matching between 'ans' takes another O(m), therefore the overall time complexity is still O(n * m)
my soln: def longestCommonPrefix(self, strs: List[str]) -> str: longest = "" for letter in strs[0]: if all([word.startswith(longest + letter) for word in strs]): longest += letter return longest
a bit late but i just wanna post my solution using typescript/javascript function longestCommonPrefix(strs: string[]): string { // take the first string as comparison let out=strs[0] // traverse the list for(let i=1;i
Why don't use sorted like others: class Solution: def longestCommonPrefix(self, v: List[str]) -> str: ans="" v=sorted(v) first=v[0] last=v[-1] for i in range(min(len(first),len(last))): if(first[i]!=last[i]): return ans ans+=first[i] return ans
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: strs.sort() i = 0 ans = "" while i < len(strs[0]) and i < len(strs[-1]) and strs[0][i] == strs[-1][i]: ans += strs[0][i] i += 1 return ans
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
How did it not hit me in my head that I needed to use 2D way of locating a character within a string withing an array of strings. It's so simple that if you don't know, makes the problem look a lot more complicated. Me brain dumb.
I don't understand how res+ = strs[0][i] would only contain what is common to all the strings. For example, when i = 2, won't res = res+strs[0][2] which is "fl"+"o". *consider the {"flower","flow","flight"} example. Some help pls
I think you're not quite seeing what strs[0][i] is actually doing. Maybe I can explain. So we have the following array/list: ["flower", "flow", "flight"] strs[0] is equal to the first string in the array/list. In other words, strs[0] = "flower" Then when you add the [i] afterwards it looks at the individual characters of that string which we are at. Since strs[0] = "flower", the [i] will loop through the word "flower" itself. So it's going to go: 'f' > 'l' > 'o' > 'w', etc. So basically, strs[0][i] is looking at the individual characters of the first word in the array/list, which in our example happens to be the word "flower", so it's going to go through each letter of the word "flower". Hope this helps!
you take the iterator as your multiplier. In this case the worst case is n for the length of strs and m in relation to the word chosen to iterator/match to. Therefore, O is O(n*m)
I believe it's because the first for loop is iterating over all of the letters in the first word which can be size 'm'. The second nested for loop is iterating through all of the words in the input array which can be size 'n'. Thus it's O(m * n). Or at least that's my understanding.
now i understand my mistake. i was comparing with the "i" in range, so 0,1,2,3 with the length, so len() which gives out 4. with the understanding they should be the same, forgot that len() gives the amount, not like an index.. damn im a noob
If there is a longer string, the prefix won't be longer than strs[0] since the prefix can at most be as long as the shortest string. The code account for shorter strings already.
Hi, I know this is a very late reply and you may have figured this out already Since we are referencing the 0'th element of strs array to initialize our loop, this element could be of any length. it could be shorter, or longer, than proceeding strings in the array. checking if i == len(s) with each iteration is a way of preventing an out-of-range error when looking at different strings in the array. Here is the thought process: We are iterating on a loop for the length of the array (strs) Say that the len(strs[0]) is equal to 5. Say we are on the 3rd iteration (i == 3) of our outer loop. in our inner loop (for s in strs:) it checks with every iteration if 'i' is equal to the length of the current string. If it IS equal, we need not to iterate again on this string, as it would cause an out-of-range error. since this would denote that we are at the ending character of 's' Hopefully this makes sense
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.
@@Century-uq8rg Not exactly since they're iterating over two different things, it's o(n*m) where n is the number of strings and m is the shortest string.
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: prefix = "" for i in range(len(strs[0])): char_to_compare = strs[0][i] for j in range(len(strs)): string = strs[j] if len(string) == i or char_to_compare != string[i]: return prefix
The time complexity of the solution in this video is: O(m * n + m^2) where n = len(strs) & m = len(strs[0]) The key thing to understand here is that the following line of code: res += strs[0][i] is an O(m) operation. (Where m = len(strs[0]) ) because `res` in the worst case scenario gets built up to the length of strs[0] and we cannot simply append a character to the end of a string like we can with a list. We have to create an entire copy of the string. I have an unlisted youtube video that shows a coaching call I had with a student that goes over why the time complexity of this solution is O(m*n + m^2), and I also mention at the end of the video how you can optimize the algorithm to be O(m*n). Or we can say O(n) if we say n = all characters of all strings within `strs`. Here's the unlisted video: ruclips.net/video/eLh5cZqNm7c/видео.html
string longestCommonPrefix(vector &strs) { string pre = ""; for (int i = 0; i < strs[0].length(); i++) { for (string &str : strs) if (i == str.length() || str[i] != strs[0][i]) return pre; pre += strs[0][i]; } return pre; }
If you sort the strings first using quicksort (or TimSort with TypeScript's Array.sort function) you get an O(nlogn) Time Complexity and then just have to compare the first and last strings (time complexity=O(m), m = length of shortest string in the list), so you get a total time complexity of O(nlogn + m) => O(nlogn) :)
I spent almost 6 hours trying to code this myself and still couldnt figure it out...lol
lol, same
That's me🥺
My man 😂 me too
I’m also spending hours in understating his solution.
Thanks guy. I'm just thought I'm the most stupid guy in the world after many hours!
Got asked this in apple today
Hey shivangi, I want to know more questions that are asked in Apple
were you able to solve it?
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]
up!
exactly what I did
But this is O(n2) time complexity right
Thanks a lot for your coding explanations. I landed a job watching your videos.
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
same bro
nice optimization.... yet the time complexity is not O(n) it is O(n*m) where n is the number of strings in the array and the m is the average length of the shortest string (found in the first loop O(n)))
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!
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 😂
I started by assigning the first element of the array strs to the prefix and then deleting the characters that didn't match.
turns out loop through a changing element is not a good idea, also in rust the delete character thing is a O(n) operation lol.
i thinked like you and i resolved it but it took 40 lines.
Man those men are amazing in simplifying the problem.
You can totally do it that way! That's how I did it:
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
shortest = min(strs, key=len)
for i, char in enumerate(shortest):
if any(s[i] != char for s in strs):
return shortest[:i]
return shortest
1. First we find the shortest string
2. Then for every string s we make sure that shortest[i] == s[i]. I use any() but a for-loop also works
3. If we don't match all characters we return shortest[:i] which is just whatever we matched so far. For example if characters 0 and 1 matched but it failed for i=2, then we return shortest[:2].
4. If we match all characters in shortest then obviously the longest common prefix is just shortest, so return that.
It takes one extra pass over the array to get the shortest string, but it doesn't change the time complexity. And it removes the edge case of checking if i goes past the length of any string.
@@davide816
min_length = min(len(s) for s in strs)
common = ""
for i in range(min_length):
for j in range(len(strs) - 1):
if strs[j][i] != strs[-1][i]:
return common
common += strs[-1][i]
return common
I did it this way. Not selecting the shortest string but selecting the length of it.
Approached it the same way. Broke my head a few times but I somehow arrived at a solution 😭
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
result = ""
count = 0
strMin = min(strs, key=len)
for i in range(len(strMin)):
for j in range(len(strs)):
if strMin[i] != strs[j][i]:
return result
else:
count += 1
if count == len(strs):
result += strMin[i]
count = 0
return result
Such a clean and concise solution..Thanks a ton
Yeah, but slow.. it requires double for loop
@@marianpascu8474 How would you do it with a single loop?
I've been using Python for about 10 years, used it for so many projects and still struggle with these tasks. It's like I have a mental block to even understanding how to start and do these.
isn't it a O(n^2) solution?
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( [ ... ] )
A string is also a type of array. There's no value added by the solution you propose here.
@@ekcelhenrichekoumelong4457 strings are immutable in python so when you append to a string, youre creating a new string which is O(n) since you have to copy the characters of the original string to the new string
c++ version:
class Solution {
public:
string longestCommonPrefix(vector& strs) {
string rsl = "";
for (int i = 0; i < strs[0].size(); i++) {
for (auto& s : strs) {
if (i == s.size() || s[i] != strs[0][i]) {
return rsl;
}
}
rsl += strs[0][i];
}
return rsl;
}
};
I usually avoid doing DSA questions using a OOPs language
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
Thanks buddy! This was the method I had in my head but I couldn’t quite figure out how to execute it.
would it be more efficient to sort the list and compare the first and the last element in the sorted list, instead of comparing every single element to the s[0]?
sorting would be O(n logn)
and comparing the first and the last element would be O(n), i believe. idk if I'm missing somethign.
class Solution(object):
def longestCommonPrefix(self, strs):
sorted_strs = sorted(strs)
res = ''
i = 0
f_str = sorted_strs[0]
l_str = sorted_strs[-1]
while i < len(f_str) and i < len(l_str):
if f_str[i] == l_str[i]:
res += f_str[i]
i+=1
else:
return res
return res
No, it has worse time complexity because you're sorting which is O(N log N). Conceptually your idea works fine though. But instead of sorting, you can use min and max in O(N) time.
shortest = min(strs)
longest = max(strs)
That'll make it roughly an optimal solution.
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
love this solution! thanks for sharing
can you please explain this solution
@@thenerdycoder07 zip(*strs) will collect all the corresponding characters from each of the given string. Number of elements in the list is the length of shortest string
Eg:
chars = zip('flower', 'flow', 'flight')
chars = [(f, f, f), (l, l, l), (o, o, i), (w, w, g)]
Then we are just iterating this chars list and checking if all elements are same:
len(set(char)) == 1
If it is, we add char to res else break as soon as we find the first mismatch
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
'''
Use the first string as the basis.
Compare each string, increment i when characters match, and update the basis.
'''
# Use the first string as the basis
basis = strs[0]
# Iterate over each string
for s in strs:
i = 0
# Increment i as long as characters match
while i < len(basis) and i < len(s) and s[i] == basis[i]:
i += 1
basis = s[:i] # Update the basis (it will get shorter)
return basis
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
basis = strs[0]
for s in strs:
i = 0
while i < len(basis) and i < len(s) and s[i] == basis[i]:
i += 1
basis = s[:i] # Update the basis
return basis
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
have you watched abdul bari's videos on KMP??
@@Vaishravana07 yes my dumbass didnt understand despite that lol
@@dhivyashri6554 yes , I recently watched the video and understood it , but I don't think I will be able to code It yet
are you preparing for your coding interview
I had the same problem and had to watch multiple different videos and read multiple articles to get it to actually make sense. I think this video was the most informative though. ruclips.net/video/GTJr8OvyEVQ/видео.html&ab_channel=TusharRoy-CodingMadeSimple
The best explanations. !!!
How about a prefix tree solution?
x = ["flower", "flosing", "flowing"]
prefix = ""
for i in range(len(x[0])):
flag = 0
temp = x[0][i]
for j in range(1, len(x)):
if not x[j][i] == temp:
flag = 0
break
else:
flag = 1
if flag ==1:
prefix+=temp
else:
pass
print(prefix)
had concept in mind. just needed a small simple how. saw your loop Nd i did it. thanks
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
If anyone confused by why he puts range(len(strs[0])) instead of the length of the shortest string, you can change your code to this one below so it fits the logic we'll iterate through the shortest string
#Find shortest string length
n = min(strs,key=len)
res = ""
for i in range(len(n)):
for char in strs:
if char[i] != strs[0][i]:
return res
res += strs[0][i]
return res
Shouldn't that be n[i] within the if condition
n = min(strs,key=len) ## shortest string
res = ""
for i in range(len(n)):
for char in strs:
if char[i] != n[i]: ## check if condition with the shortest string
return res
res += n[i]
return res
The loop will break once it reaches the shortest string "i == len(s)"
U a God- My implementation with a Trie in Python:
class TrieNode:
def __init__(self):
self.child = {}
self.count = 1
class Solution(object):
def __init__(self):
self.root = TrieNode()
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
for word in strs:
self.insert(word) # create the Trie
total_strs = len(strs) # {'fl': 3}
ans = []
word = strs[0] # use to find the common prefix in the Trie
curr = self.root
for ch in word:
if ch in curr.child and curr.child[ch].count == total_strs:
ans.append(ch)
curr = curr.child[ch]
else:
break # no common prefix among the input strings
return "".join(ans)
def insert(self, word):
curr = self.root
for ch in word:
if ch not in curr.child:
curr.child[ch] = TrieNode()
else:
curr.child[ch].count += 1
curr = curr.child[ch]
res=''
for i in range(0,len(strs[0])):
for s in range(len(strs)):
if i==len(strs[s]) or strs[s][i]!= strs[0][i]:
return res
res= res+strs[s][i]
return res
This code looks more readable and understandable
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."
Are you certain about the matching in step 2-4? I think if you iterate through string 1 by 1, it takes O(n). Then the index matching between 'ans' takes another O(m), therefore the overall time complexity is still O(n * m)
This should be your style~~
prefix = strs[0]
for i in range(1, len(strs)):
while not strs[i].startswith(prefix):
prefix = prefix[0:-1]
return prefix
idk about that... that solution looks way more complicated
this is cheating AF
my soln:
def longestCommonPrefix(self, strs: List[str]) -> str:
longest = ""
for letter in strs[0]:
if all([word.startswith(longest + letter) for word in strs]):
longest += letter
return longest
a bit late but i just wanna post my solution using typescript/javascript
function longestCommonPrefix(strs: string[]): string {
// take the first string as comparison
let out=strs[0]
// traverse the list
for(let i=1;i
thanks for the code i was trying to do this but wasn't able to
Why don't use sorted like others:
class Solution:
def longestCommonPrefix(self, v: List[str]) -> str:
ans=""
v=sorted(v)
first=v[0]
last=v[-1]
for i in range(min(len(first),len(last))):
if(first[i]!=last[i]):
return ans
ans+=first[i]
return ans
Thank you so much!
What if we sort the list, this way it will automatically have common prefixes arranged and we can just check the first and last one
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
strs.sort()
i = 0
ans = ""
while i < len(strs[0]) and i < len(strs[-1]) and strs[0][i] == strs[-1][i]:
ans += strs[0][i]
i += 1
return ans
isnt this brute force approach with time complextiy of O(n2) ? How is this optimal ?
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
How did it not hit me in my head that I needed to use 2D way of locating a character within a string withing an array of strings. It's so simple that if you don't know, makes the problem look a lot more complicated. Me brain dumb.
damn, you made it look so simple
Incredible! Thank you!
I don't understand how res+ = strs[0][i] would only contain what is common to all the strings. For example, when i = 2,
won't res = res+strs[0][2] which is "fl"+"o".
*consider the {"flower","flow","flight"} example.
Some help pls
I think you're not quite seeing what strs[0][i] is actually doing. Maybe I can explain.
So we have the following array/list: ["flower", "flow", "flight"]
strs[0] is equal to the first string in the array/list. In other words, strs[0] = "flower"
Then when you add the [i] afterwards it looks at the individual characters of that string which we are at. Since strs[0] = "flower", the [i] will loop through the word "flower" itself. So it's going to go: 'f' > 'l' > 'o' > 'w', etc.
So basically, strs[0][i] is looking at the individual characters of the first word in the array/list, which in our example happens to be the word "flower", so it's going to go through each letter of the word "flower".
Hope this helps!
I have the same doubt, it is like comparing first and second string, but how we are taking common between 2nd and third string here
could you reiterate concept of inbound and outbound?
we are using for loop inside another for loop. isnt the time complexity n2? Exponential
you take the iterator as your multiplier. In this case the worst case is n for the length of strs and m in relation to the word chosen to iterator/match to. Therefore, O is O(n*m)
Nice video. But i believe it would be better to teach an O(n) solution instead of O(n^2).
this is an O(n) solution even though there are indented for loops.
I thought this was asking longest common substring this whole time.... i need to sleep
Why isn't the time complexity O(n^2)? There's a nested for loop
I believe it's because the first for loop is iterating over all of the letters in the first word which can be size 'm'. The second nested for loop is iterating through all of the words in the input array which can be size 'n'.
Thus it's O(m * n).
Or at least that's my understanding.
plz add typescript support in neetcode
why did you wrote != strs[0][i] ?
Because if it is equal then we will keep checking next indexes
now i understand my mistake.
i was comparing with the "i" in range, so 0,1,2,3 with the length, so len() which gives out 4. with the understanding they should be the same, forgot that len() gives the amount, not like an index..
damn im a noob
Awesome explanation
Did it work? Yes. Did it make sense? No.
why is it strs[0] ?
what if there is another string that is bigger ? or shorter ?
What I was thinking also... Maybe problem just assumes first str is longest?
I think it doesn't matter. This could be arbitrary string in the array. i == len(s) and the immediate return check the min length of strings.
My first solution had this: word = min(strs, key=len)
If there is a longer string, the prefix won't be longer than strs[0] since the prefix can at most be as long as the shortest string. The code account for shorter strings already.
Aren't these two for loops nested, hence o(n^2)?
No, It's O(n⋅m), where n - number of strings, and m - average length of the strings
@@user-we5lp1yr3r It makes sense now. Thank you!
im not sure how you added I == Len(s) *what purpose it serves
Hi, I know this is a very late reply and you may have figured this out already
Since we are referencing the 0'th element of strs array to initialize our loop, this element could be of any length. it could be shorter, or longer, than proceeding strings in the array.
checking if i == len(s) with each iteration is a way of preventing an out-of-range error when looking at different strings in the array.
Here is the thought process:
We are iterating on a loop for the length of the array (strs)
Say that the len(strs[0]) is equal to 5.
Say we are on the 3rd iteration (i == 3) of our outer loop.
in our inner loop (for s in strs:) it checks with every iteration if 'i' is equal to the length of the current string.
If it IS equal, we need not to iterate again on this string, as it would cause an out-of-range error. since this would denote that we are at the ending character of 's'
Hopefully this makes sense
does there exist a linear solution?
Not possible (under the definition). Worst case you have the nearly the same words so it'd be O(n*m).
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.
time complexity is o of n squared as there two nested for loops
@@Century-uq8rg Not exactly since they're iterating over two different things, it's o(n*m) where n is the number of strings and m is the shortest string.
@@taylorman1111 I agree with you.
How tf this is easy?😭😭
Thanks for the video))
I believe it would be faster by sorting an array and grabbing first and last words only for prefix comparison
No, it would actually be slower. You’d have to pass through the array again to sort the elements, which would add to the runtime
I copied the exact same code and still it's not working😭. I have spent my whole night into this. If someone succeed pls comment down the code.
Check for indentation
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
prefix = ""
for i in range(len(strs[0])):
char_to_compare = strs[0][i]
for j in range(len(strs)):
string = strs[j]
if len(string) == i or char_to_compare != string[i]:
return prefix
prefix += char_to_compare
return prefix
The time complexity of the solution in this video is: O(m * n + m^2) where n = len(strs) & m = len(strs[0])
The key thing to understand here is that the following line of code:
res += strs[0][i]
is an O(m) operation. (Where m = len(strs[0]) ) because `res` in the worst case scenario gets built up to the length of strs[0] and we cannot simply append a character to the end of a string like we can with a list. We have to create an entire copy of the string.
I have an unlisted youtube video that shows a coaching call I had with a student that goes over why the time complexity of this solution is O(m*n + m^2), and I also mention at the end of the video how you can optimize the algorithm to be O(m*n). Or we can say O(n) if we say n = all characters of all strings within `strs`.
Here's the unlisted video: ruclips.net/video/eLh5cZqNm7c/видео.html
how can you say its O(n) when you have nested loops lol. Its O(n*m)
Thanks!
Thank you 🙏
is this Easy problem?
For some have background but for beginners 😂😂😂😂😂
can anyone provide a c++ solution for this?
thanks
string longestCommonPrefix(vector &strs)
{
string pre = "";
for (int i = 0; i < strs[0].length(); i++)
{
for (string &str : strs)
if (i == str.length() || str[i] != strs[0][i])
return pre;
pre += strs[0][i];
}
return pre;
}
BEAUTIFUL
I did not understand the code
You sound like jeany collects
We can just sort the list of string first then can use the for loop it will be more easy
🎉
If you sort the strings first using quicksort (or TimSort with TypeScript's Array.sort function) you get an O(nlogn) Time Complexity and then just have to compare the first and last strings (time complexity=O(m), m = length of shortest string in the list), so you get a total time complexity of O(nlogn + m) => O(nlogn) :)
Love your content
I was hoping for a TRIE solution explanation..
I still dont understand this man :(
same here..i too didn't understand...
@@farjanashaik9601 @Anon Try to visualise what happens on every iteration. Use Print statements or Pycharm Debugger.
my interview question🥲
Interview where?
Thank you so much!
Thank you so much!