CODEWITHSUNDEEP
pythonpython-3.xstringlistsubstring
momo123321
momo123321

Reputation: 155

Write a function to find the longest common prefix string amongst an array of strings. Index out of range

I am doing a problem where i need to Write a function to find the longest common prefix string amongst an array of strings.
For example :

Input: strs = ["flower","flow","flight"]
Output: "fl"

What I am trying to do, is check each letter indiviudally of each word to see if they are equal. and when they are not then I know that at that moment we have the longest common prefix.After brainstorming for a while, this was the best i could to and went with this idea. However, once I finished my code, it seems to work for some arrays, but most of the time I have an index out of range error. I went to python visualizer to see where I go wrong but everytime I try to change something I get an index error but for a different reason. so after hours of debugging, i gave up and i am now asking for your help to solve this index problem. for example an index error occurs when i have this array : [ "ab" , "a" ] and more. Im pretty sure my idea is code and my code almost works, so im just asking how to change it, not an entire new code. Thank you
This is my code :

strs = ["ab","a"]
def longestCommonPrefix(strs):
    for word in strs:
        if word == "":
            return ""
    if len(strs) == 1:
        return strs[0]
    common_prefix = ""
    j = 0
    Common = True
    while Common:
        for i in range(len(strs) - 1):
            if strs[i][j] != strs[i + 1][j]:
                Common = False
                break
        else:
            common_prefix += strs[0][j]
            j += 1
    return common_prefix
print(longestCommonPrefix(strs))

Upvotes: -2

Views: 2633

Answers (4)

Synapse
Synapse

Reputation: 1665

Easiest and simplest way:

# Use the first string as a reference
reference = strs[0]
for i in range(len(reference)):
    for string in strs[1:]:
        if i >= len(string) or string[i] != reference[i]:
            return reference[:i]
return reference

Upvotes: 0

dyson
dyson

Reputation: 44

strings = ["a", "ab"]

def find_longest_prefix(data):
    shortest_word = min(data, key=len)

    for prefix_slice_end in range(len(shortest_word), 0, -1):
        if all(i.startswith(shortest_word[0:prefix_slice_end]) for i in data):
            return shortest_word[0:prefix_slice_end]

    return ''

print(find_longest_prefix(strings))
# >> a

Upvotes: 2

Ahmed Salman
Ahmed Salman

Reputation: 271

   def longestCommonPrefix(strs):
      if len(strs) == 0:
         return ""
      current = strs[0]
      for i in range(1,len(strs)):
         temp = ""
         if len(current) == 0:
            break
         for j in range(len(strs[i])):
            if j<len(current) and current[j] == strs[i][j]:
               temp+=current[j]
            else:
               break
         current = temp
      return current
input_list = ["school","schedule","scotland"]
print(longestCommonPrefix(input_list))

Upvotes: 1

Sharim09
Sharim09

Reputation: 6214

The error is because all strings in the lst do not have the same length, so if you loop over one string length, there might be a chance that some strings have lengths smaller than this. So while using the if condition, try and except block the check for the IndexError.

Try this

strs = ["ab", "a"]


def longestCommonPrefix(strs):
    for word in strs:
        if word == "":
            return ""
    if len(strs) == 1:
        return strs[0]
    common_prefix = ""
    j = 0
    Common = True
    while Common:
        for i in range(len(strs) - 1):
            try:
                if strs[i][j] != strs[i + 1][j]:
                    Common = False
                    break
            except IndexError:
                Common = False
                break
        else:
            common_prefix += strs[0][j]
            j += 1
    return common_prefix


print(longestCommonPrefix(strs))

If you want some other way then use this one.


def longestCommonPrefix(lst):
    for a in range(1, len(lst[0])):
        try:
            if not all(letter.startswith(lst[0][:a]) for letter in lst[1:]):
                return lst[0][:a-1]

        except IndexError:
            return lst[0][:a-1]

    return ""
lst = ["flower", "flow", "flight"]
print(longestCommonPrefix(lst))

Upvotes: 1

Related Questions