Home > Mobile >  Why is my function returning two duplicate values?
Why is my function returning two duplicate values?

Time:04-12

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 ''
  • Related