class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if len(strs)==0: pref='' else: L=[] for text in strs: num=len(text) L.append(num) count=min(L) for j in range(count+1): S = [] for text in strs: t=text[0:j] S.append(t) if len(set(S))
What if the second string in the array is longer than the first? Then common prefix could be longer than the pref, and you would have to insert addition. On the other hand, if the array of strings is sorted so that strings are getting shorter as their index is bigger, than line 14 would give you an Out of Range error, because plen would be bigger than the len(second_string). Finally, if there is no common prefix between first and the second string in the array, plen should be 0 and search would stop because of the return command. And that would likely give a wrong result. But, according to LeetCode everything is OK. What is going on here?
Hi, please find the below explanation 1. If the second string is longer than the first, we would not add anything to the prefix, since we have to find 'common' present in all three and it cannot be bigger than the shortest string in the array. So even if the length of the second is greater, the prefix will still be the shorter one since it's present in both. 2. Python does not give you an error if you try to slice up a string after it's the length. Check the output of this. If a ='flower' then 'print(a[0:20])' will not give an error instead just print flower. 3. If there is no prefix we are using return("") i.e an empty string . It does not give a wrong answer.
It could be O(n*m) where N is the number of strings in the array and m is the number of times it has to repeat the while (there should be a better way to name m)
while pref != s[0:plen] , what happens if pref is contained in s , just not in the [0:plen] portion ? , for example (car,teslacar) , u would have that car != teslacar[0:3] , and then shorten car into ca , yet car is a common prefix
Short and crisp solution 👍
easiest explanation! keep it up
Glad it helped!
Nice solution! easy to understand
THANKS SIR! :)
Great video! What about time and space complexity? I have simplified a bit your solution:
class Solution(object):
def longestCommonPrefix(self, strs):
if len(strs)==0:
return("")
if len(strs)==1:
return(strs[0])
pref = strs[0]
plen = len(strs[0])
for s in strs[1:]:
while pref != s[:plen]:
pref = pref[:-1]
plen = len(pref)
if plen ==0:
return("")
return pref
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if len(strs)==0:
pref=''
else:
L=[]
for text in strs:
num=len(text)
L.append(num)
count=min(L)
for j in range(count+1):
S = []
for text in strs:
t=text[0:j]
S.append(t)
if len(set(S))
Thank you for the video. Question: what if the array was ['common', ' desend', 'decent'], would the codes find out the longest prefix which is "de"?
nope, there is not common prefix
THANKS man Appretiated
Great solution!
Clear and nice explanation, can you please tell the time complexity?
What if the second string in the array is longer than the first? Then common prefix could be longer than the pref, and you would have to insert addition. On the other hand, if the array of strings is sorted so that strings are getting shorter as their index is bigger, than line 14 would give you an Out of Range error, because plen would be bigger than the len(second_string). Finally, if there is no common prefix between first and the second string in the array, plen should be 0 and search would stop because of the return command. And that would likely give a wrong result. But, according to LeetCode everything is OK. What is going on here?
Hi, please find the below explanation
1. If the second string is longer than the first, we would not add anything to the prefix, since we have to find 'common' present in all three and it cannot be bigger than the shortest string in the array. So even if the length of the second is greater, the prefix will still be the shorter one since it's present in both.
2. Python does not give you an error if you try to slice up a string after it's the length. Check the output of this. If a ='flower' then 'print(a[0:20])' will not give an error instead just print flower.
3. If there is no prefix we are using return("") i.e an empty string . It does not give a wrong answer.
for example if in list ['l'.'love''lost.'life'] so the common prefix is only 'l' so we do not need a long word to check
thank you! what would be the time complexity for this since the while loop might shorten each time? still O(N^2)?
It could be O(n*m) where N is the number of strings in the array and m is the number of times it has to repeat the while (there should be a better way to name m)
wonderful😀
best explanation tyvm
while pref != s[0:plen] , what happens if pref is contained in s , just not in the [0:plen] portion ? , for example (car,teslacar) , u would have that car != teslacar[0:3] , and then shorten car into ca , yet car is a common prefix
prefix is at the beginning of the word
best explanation
What is space and time complexity here?
is this a brute force way to search for the elements or a different technique?
former
Could somebody please explain this line: "while pref != s[0:plen]". What exactly does this condition mean?
Instead of checking the whole string characters of s, it checks only for the length of the prefix.
an easy solution but not efficient
Sometimes easy is the most efficient.
how would you make it more efficient?