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

Question

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

Does this answer your question? [Determine prefix from a set of (similar) strings](https://stackoverflow.com/questions/6718196/determine-prefix-from-a-set-of-similar-strings) — Claudio, Jan 02 '23 at 20:15
searching stackoverflow for "longest common prefix python" gives 49 results. It's a leetcode problem 14. question, last asked 2 days ago here https://stackoverflow.com/questions/74968036/leetcode-problem-14-longest-common-prefix-python . — Claudio, Jan 02 '23 at 20:23
@Claudio no it doesnt. i did not post this to know how to do the problem. i posted this to know why my specific solution didnt work. i know there are tons of tutorial online on how to do this problem. but I wanted it to figure it out by myself at first. — momo123321, Jan 02 '23 at 20:31

dyson · Answer 1 · 2023-01-02T19:18:25.253

2

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

edited Jan 02 '23 at 19:18

answered Jan 02 '23 at 19:09

dyson

29
4

bruh you add a `data` parameter but you never use it. – codester_09 Jan 02 '23 at 19:12
ok yeah, now that's properly used and it also works for those cases. – dyson Jan 02 '23 at 19:18

score 1 · Accepted Answer · answered Jan 02 '23 at 19:09

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

it works. thanks. do you know what would be the time complexity of this program? I would say O(n) because you only loop through the array once but I don't know if try and except changes the time complexity since I didn't even know this function existed. . thanks again — momo123321, Jan 02 '23 at 19:19
@momo123321 Time Complexity is `O(n)`. No, they aren't changing the time complexity. Also, [`try-except`](https://w3schools.com/python/python_try_except.asp) isn't function. — codester_09, Jan 02 '23 at 19:25

Ahmed Salman · Answer 3 · 2023-01-02T19:16:19.097

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

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

3 Answers3