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'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.
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
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
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
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
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)
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
First solution came to my mind was to take first string from array, then compare it with the rest of the strings in the array. But i got lost while writing the code 😭
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
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
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
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.
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]
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
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)
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
im pretty sure its O(n*m) since we are bounded by the length of our strs[0] = n and then the size of our array of string = m so its n*m. Since the size of the starting string and our length of the array of strings is not the same variable.
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
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. th-cam.com/video/GTJr8OvyEVQ/w-d-xo.html&ab_channel=TusharRoy-CodingMadeSimple
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.
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: th-cam.com/video/eLh5cZqNm7c/w-d-xo.html
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
For all the CS student in here, you can just create a Trie here lmao Time Complexity Analysis: O(n*m) - to create the Trie Data structure with strs O( len(prefix) ) - to actually find the prefix
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
the problem with it is the usage of space, i thought so too at first using the following code, preserve you from saving any data , leading to O(1) space , same complexity # length of the first string letters for i in range(len(strs[0])): # check each string if it stil follows the same prefix for j in range(1,len(strs)): # first word is longer or different letter in i if i == len(strs[j]) or strs[j][i] != strs[0][i]: return strs[0][:i] return strs[0]
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
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.
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 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!
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
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 it has to be n*2 so why not make it cooler. Behold my monstrosity. class TrieNode: def __init__(self): self.children = [None] * 26 self.is_leaf = False class Trie: def __init__(self, seed): self.root = TrieNode() current = self.root for c in seed: index = ord(c) - ord('a') current.children[index] = TrieNode() current = current.children[index] current.is_leaf = True def prefix_check(self, word): current = self.root result = "" for c in word: if current.is_leaf: return result index = ord(c) - ord('a') if current.children[index] == None: current.children = [None] * 26 current.is_leaf = True return result result = result + c current = current.children[index] current.children = [None] * 26 current.is_leaf = True return result class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if len(strs) == 1: return strs[0] trie = Trie(strs[0]) result = "" for word in strs: result = trie.prefix_check(word) return result
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?
Is it true? And what solution did you give them? Were they satisfied or asked to optimize it. Please let us know!
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
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)))
I am really relived after reading the comment. It helps me not to lose my hope. I am not dumb, I am not dumb, I am not dumb, I can do this.
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.
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
Thanks a lot for your coding explanations. I landed a job watching your videos.
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!
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?
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
@@leonlin41618 not the solution found in the video
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)"
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
@@asjadmulani9640nothing great abt it
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
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)
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.
I came up with the exact solution in an hour before watching this. Was looking to see if there is any better algorithm than this tho.
First solution came to my mind was to take first string from array, then compare it with the rest of the strings in the array. But i got lost while writing the code 😭
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
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
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
had concept in mind. just needed a small simple how. saw your loop Nd i did it. thanks
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
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.
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]
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
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)
The best explanations. !!!
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
isn't it a O(n^2) solution?
im pretty sure its O(n*m) since we are bounded by the length of our strs[0] = n and then the size of our array of string = m so its n*m. Since the size of the starting string and our length of the array of strings is not the same variable.
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
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. th-cam.com/video/GTJr8OvyEVQ/w-d-xo.html&ab_channel=TusharRoy-CodingMadeSimple
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.
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: th-cam.com/video/eLh5cZqNm7c/w-d-xo.html
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
For all the CS student in here, you can just create a Trie here lmao
Time Complexity Analysis:
O(n*m) - to create the Trie Data structure with strs
O( len(prefix) ) - to actually find the prefix
Did it work? Yes. Did it make sense? No.
I thought this was asking longest common substring this whole time.... i need to sleep
damn, you made it look so simple
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.
Thank you so much!
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
Thanks for the video))
How about a prefix tree solution?
the problem with it is the usage of space, i thought so too at first
using the following code, preserve you from saving any data , leading to O(1) space , same complexity
# length of the first string letters
for i in range(len(strs[0])):
# check each string if it stil follows the same prefix
for j in range(1,len(strs)):
# first word is longer or different letter in i
if i == len(strs[j]) or strs[j][i] != strs[0][i]:
return strs[0][:i]
return strs[0]
How tf this is easy?😭😭
could you reiterate concept of inbound and outbound?
Incredible! Thank you!
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
Awesome explanation
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)
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.
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) :)
Thanks!
Thank you 🙏
plz add typescript support in neetcode
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
BEAUTIFUL
isnt this brute force approach with time complextiy of O(n2) ? How is this optimal ?
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
@@АндрійГнатущенко-ч9и It makes sense now. Thank you!
We can just sort the list of string first then can use the for loop it will be more easy
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.
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
Love your content
why did you wrote != strs[0][i] ?
Because if it is equal then we will keep checking next indexes
how can you say its O(n) when you have nested loops lol. Its O(n*m)
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).
You sound like jeany collects
i knew the logic but dont knwo how to code for it ! 😭😭😭😭
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.
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
very poor string handling. should do it via list
I did not understand the code
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;
}
🎉
is this Easy problem?
For some have background but for beginners 😂😂😂😂😂
I was hoping for a TRIE solution explanation..
If it has to be n*2 so why not make it cooler.
Behold my monstrosity.
class TrieNode:
def __init__(self):
self.children = [None] * 26
self.is_leaf = False
class Trie:
def __init__(self, seed):
self.root = TrieNode()
current = self.root
for c in seed:
index = ord(c) - ord('a')
current.children[index] = TrieNode()
current = current.children[index]
current.is_leaf = True
def prefix_check(self, word):
current = self.root
result = ""
for c in word:
if current.is_leaf:
return result
index = ord(c) - ord('a')
if current.children[index] == None:
current.children = [None] * 26
current.is_leaf = True
return result
result = result + c
current = current.children[index]
current.children = [None] * 26
current.is_leaf = True
return result
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs) == 1:
return strs[0]
trie = Trie(strs[0])
result = ""
for word in strs:
result = trie.prefix_check(word)
return result
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!