I'm doing a practice problem where I need to find the longest common prefix in a list of strings.
Example:
Input: strs = ["flower","flow","flight"]
Output: "fl"
I'm approaching this as follows:
def my_function(strs):
### get the length of shortest string in list and assign to "window"
min_len = min([len(x) for x in strs])
window = min_len
### chop all items in list to length of shortest item
for i in range(window):
if window == 0:
return ''
strs = [x[:window] for x in strs]
### Check the length of the set() of all items. If it's longer than 1,
### shorten the window and re-check
if len(set(strs)) == 1:
answer = list(set(strs))
return answer[0]
else:
window = -1
When I use the test case given above, my function returns:
fl
fl
Why am I getting this duplication?
CodePudding user response:
You're using a word loop where you increment "window" with the "for", but decrement it based on a condition. This causes an inconsistent iteration.
Either use a while
loop and modify the counter manually, or use a for
loop and don't modify the counter.
That said your approach of not so efficient, rather check the characters in parallel position after position:
def prefix(strs):
out = []
for x in zip(*strs):
if len(set(x)) == 1:
out.append(x[0])
else:
break
return ''.join(out)
prefix(strs)
Output: 'fl'
CodePudding user response:
With @mozway's help, I was able to successfully execute the function using a while
statement:
def prefix(strs):
min_len = min([len(x) for x in strs])
window = min_len
for i in range(window):
while window > 0:
strs = [x[:window] for x in strs]
if len(set(strs)) == 1:
answer = list(set(strs))
return answer[0]
else:
window = -1
return ''