Longest Common Prefix - Leetcode 14 - Python

[@blankomog]

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

[@hannanabdullah8842]

lol, same

[@anshumansharma1069]

That's me🥺

[@adityasarve275]

My man 😂 me too

[@JimZarasOfficial]

I’m also spending hours in understating his solution.

[@nguyenkhoanam8930]

Thanks guy. I'm just thought I'm the most stupid guy in the world after many hours!

[@ShivangiSingh-wc3gk]

Got asked this in apple today

[@shivanidhyani8370]

Hey shivangi, I want to know more questions that are asked in Apple

[@musasu]

were you able to solve it?

[@thepriestofvaranasi]

Is it true? And what solution did you give them? Were they satisfied or asked to optimize it. Please let us know!

[@jlau04]

Accenture also asks this

[@OfficialRehaldinho64]

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]

[@Rajmanov]

up!

[@martinlacsamana7534]

exactly what I did

[@vishaalkumaranandan2894]

But this is O(n2) time complexity right

[@angeldiaz3018]

i prefer neetcode's solution my boy

[@ballayran9321]

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.

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

[@tsunami8892]

same bro

[@jassemtoumi8748]

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

[@grub_taless7561]

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 😂

[@aperson4475]

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.

[@davide816]

i thinked like you and i resolved it but it took 40 lines. Man those men are amazing in simplifying the problem.

[@nikhil_a01]

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.

[@selim7372]

​@@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.

[@ielinDaisy]

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

[@arayofcode]

My first approach was inserting all elements to a radix tree, and returning the root (empty string in default case). However, the time complexity was the same as the approach shared above and takes O(m * n) time. So to optimize it, I tried a variant of binary search where I'm checking prefix length: ``` low = 0, high = shortestString(strs) mid = (low + high) / 2 while low < high { if isCommonPrefix(strs, mid) { low = mid + 1 } else { high = mid - 1 } mid = (low + high)/2 } return strs[:mid] // isCommonPrefix iterates through all strings in strs, and checks if str[:mid] is a common prefix // shortestString searches through all strings in strs and returns length of the smallest string ``` This should take O(n log m) if I understand correctly?

[@elizabethr5161]

Such a clean and concise solution..Thanks a ton

[@marianpascu8474]

Yeah, but slow.. it requires double for loop

[@darellarocho5729]

@@marianpascu8474 How would you do it with a single loop?

[@rachanaacharya943]

Thanks a lot for your coding explanations. I landed a job watching your videos.

[@pranit_1643]

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!

[@TheWeightliftingTriathlete]

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.

[@SleeplessWrestling]

you have to map it out first without code and determine some approaches

[@TheWeightliftingTriathlete]

@SleeplessWrestling thanks - been doing that and the more I see videos/try, the better I'm getting. I've noticed I'm getting a lot better at spotting the "edge cases" and dealing with that first. Eg if there's just a single value input, then return or exit

[@harunguven8581]

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]

A string is also a type of array. There's no value added by the solution you propose here.

[@uberandrew123456]

@@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

[@hitash5395]

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; } };

[@asjadmulani9640]

I usually avoid doing DSA questions using a OOPs language

[@navoditranjan7247]

@@asjadmulani9640nothing great abt it

[@DanielTruongDev]

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

[@antrikshsingh7798]

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

[@stevenlam1606]

The loop will break once it reaches the shortest string "i == len(s)"

[@leonlin41618]

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

[@leonlin41618]

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

[@Turnpost2552]

@@leonlin41618 not the solution found in the video

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

[@eltonsilvamtm2]

love this solution! thanks for sharing

[@thenerdycoder07]

can you please explain this solution

[@VarunMittal-viralmutant]

@@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

[@julianrendon1152]

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

[@googoo725]

Thanks buddy! This was the method I had in my head but I couldn’t quite figure out how to execute it.

[@huzaifanaseerkhan]

isn't it a O(n^2) solution?

[@dilhfvesgetg6192]

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.

[@mehmetnadi8930]

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

[@nikhil_a01]

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.

[@OlegVendeland-cu2or]

Thanks!

[@NeetCode]

Thank you 🙏

[@Abhishek-ji6qj]

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)

[@hadizorkot2889]

The topics of this question include Trie. I was wondering how the implementation would look like using a Trie. Also, how would time complexity be affected?

[@dhivyashri6554]

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

[@Vaishravana07]

have you watched abdul bari's videos on KMP??

[@dhivyashri6554]

@@Vaishravana07 yes my dumbass didnt understand despite that lol

[@Vaishravana07]

@@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

[@nikobekris8542]

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. kzbin.info/www/bejne/fYWto2uFq954jLM&ab_channel=TusharRoy-CodingMadeSimple

[@gmoney_swag1274]

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

[@AnnieBox]

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

[@Jr-xs9hy]

idk about that... that solution looks way more complicated

[@Rajmanov]

this is cheating AF

[@jameszhang8569]

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.

[@vishaks9642]

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

[@annakarelina3365]

The best explanations. !!!

[@aficachi]

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: kzbin.info/www/bejne/m33LZpaQprOgbcU

[@yauhensedliarou826]

How about a prefix tree solution?

[@galnadjar]

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]

[@jand2861]

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

[@commonguy7]

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

[@mahmoodali1871]

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

[@a.d.a.k2143]

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

[@darellarocho5729]

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!

[@priyak3133]

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

[@watchlistsclips3196]

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

[@crimsonghoul8983]

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.

[@ShubhamBhatt-j7u]

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 😭

[@nitingupta1650]

we are using for loop inside another for loop. isnt the time complexity n2? Exponential

[@jacobw9647]

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)

[@jpkeys6000]

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

[@АндрійГнатущенко-ч9и]

No, It's O(n⋅m), where n - number of strings, and m - average length of the strings

[@jpkeys6000]

@@АндрійГнатущенко-ч9и It makes sense now. Thank you!

[@alifhanafiah]

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

[@vaibhavmundhra1997]

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

[@sangpark7656]

could you reiterate concept of inbound and outbound?

[@jeezradz]

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

[@clomz213]

What I was thinking also... Maybe problem just assumes first str is longest?

[@yingyuan589]

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.

[@roshanzameer5020]

My first solution had this: word = min(strs, key=len)

[@hassannajam4634]

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.

[@ayo4590]

Why isn't the time complexity O(n^2)? There's a nested for loop

[@drewskii9708]

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.

[@kvtys]

I thought this was asking longest common substring this whole time.... i need to sleep

[@rgb8534]

why did you wrote != strs[0][i] ?

[@shalinisangal84]

Because if it is equal then we will keep checking next indexes

[@edwardteach2]

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]

[@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.

[@Century-uq8rg]

time complexity is o of n squared as there two nested for loops

[@taylorman1111]

@@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.

[@shashanksharma7242]

@@taylorman1111 I agree with you.

[@christmas7056]

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."

[@lapwamen1913]

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)

[@snake1625b]

does there exist a linear solution?

[@pedrov8868]

Not possible (under the definition). Worst case you have the nearly the same words so it'd be O(n*m).

[@ombothre2350]

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

[@ombothre2350]

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

[@kippe1221]

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

[@martinsauer5311]

Nice video. But i believe it would be better to teach an O(n) solution instead of O(n^2).

[@jingwang2111]

this is an O(n) solution even though there are indented for loops.

[@sangpark7656]

im not sure how you added I == Len(s) *what purpose it serves

[@buhnanner2935]

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

[@lahiruweliwitiya2]

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

[@cryptshar6759]

damn, you made it look so simple

[@joshipiano]

isnt this brute force approach with time complextiy of O(n2) ? How is this optimal ?

[@Vijay-bs2gf]

Incredible! Thank you!

[@edwythefair5215]

Thank you so much!

[@parijatbandyopadhyay8057]

Awesome explanation

[@anatoliy-gr]

Thanks for the video))

[@mcspraint]

plz add typescript support in neetcode

[@vishwanath-ts]

How tf this is easy?😭😭

[@tryingtobeproductive]

Did it work? Yes. Did it make sense? No.

[@ezrachua1317]

how can you say its O(n) when you have nested loops lol. Its O(n*m)

[@pranav5273]

I did not understand the code

[@musasu]

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.

[@abhinavkuppasad2720]

Check for indentation

[@damonfernandez3051]

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

[@johnlocke4695]

You sound like jeany collects

[@jarjarbinks8954]

can anyone provide a c++ solution for this? thanks

[@primogem_160]

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; }

[@suryodhan3060]

i knew the logic but dont knwo how to code for it ! 😭😭😭😭

[@brandonsager223]

BEAUTIFUL

[@SailorMan1000]

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

[@suar_pilla]

is this Easy problem?

[@VinceMichaelDizon]

For some have background but for beginners 😂😂😂😂😂

[@yashshukla1637]

very poor string handling. should do it via list

[@shivanidhyani8370]

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

[@ayuanzhao7062]

my interview question🥲

[@doc9448]

Interview where?

[@ИринаГусев-р9ю]

Love your content

[@lukaszplachecki8723]

🎉

[@deepakthakur8781]

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

[@abhishekshah4443]

I was hoping for a TRIE solution explanation..

[@moezzzz9341]

I still dont understand this man :(

[@farjanashaik9601]

same here..i too didn't understand...

[@roshanzameer5020]

@@farjanashaik9601 @Anon Try to visualise what happens on every iteration. Use Print statements or Pycharm Debugger.

[@FaberLSH]

Thank you so much!

[@ksvignesh1906]

Thank you so much!