Longest Common Prefix with Python

Viewed 934

I am trying to figure out an easy leetcode question and I do not know why my answer does not work. Problem: Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". My Code:

shortest=min(strs,key=len)
strs.remove(shortest)
common=shortest
for i in range(1,len(shortest)):
    comparisons=[common in str for str in strs]
    if all(comparisons):
        print(common)
        break
    else:
        common=common[:-i]

The above trial does not work when the length of the strings in the list are same but works for other cases. Thank you very much.

6 Answers

Friend, try to make it as 'pythonic' as possible. just like you would in real life.

in real life what do you see? you see words and maybe look for the shortest word and compare it to all the others. Okay, let's do that, let's find the longest word and then the shortest.

First we create an empty string, there the characters that are the same in both strings will be stored

prefix = ''
#'key=len' is a necesary parameter, because otherwise, it would look for the chain with the highest value in numerical terms, and it is not always the shortest in terms of length (it is not exactly like that but so that it is understood haha)
max_sentense = max(strings, key=len)
min_sentense = min(strings, key=len)

Okay, now what would we do in real life? loop both one by one from the beginning, is it possible in python? yes. with zip()

for i, o in zip(max_sentense, min_sentense):

the 'i' will go through the longest string and the 'o' will go through the shortest string.

ok, now it's easy, we just have to stop going through them when 'i' and 'o' are not the same, that is, they are not the same character.

for i, o in zip(max_sentense, min_sentense):

        if i == o:
            prefix += i
        else:
            break

full code:

prefix = ''


    max_sentense = max(strings, key=len)
    min_sentense = min(strings, key=len)

    for i, o in zip(max_sentense, min_sentense):

        if i == o:
            prefix += i
        else:
            break
print(prefix)

It's quickest to compare the first characters of all the words, and then the second characters, etc. Otherwise you're doing unnecessary comparisons.

def longestCommonPrefix(self, strs):
    prefix = ''
    for char in zip(*strs):
        if len(set(char)) == 1:
            prefix += char[0]
        else:
            break
    return prefix

You can do this fairly efficiently in a single iteration over the list. I've made this a little verbose so that it's easier to understand.

import itertools

def get_longest_common_prefix(strs):
    longest_common_prefix = strs.pop()
    for string in strs:
        pairs = zip(longest_common_prefix, string)
        longest_common_prefix_pairs = itertools.takewhile(lambda pair: pair[0] == pair[1], pairs)
        longest_common_prefix = (x[0] for x in longest_common_prefix_pairs)
    return ''.join(longest_common_prefix)

In your code you cross check with the shortest string which can be one of the shortest strings if multiple same length strings are present. Furthermore the shortest might not have the longest common prefix.


This is not a very clean code but it does the job

common, max_cnt = "", 0 
for i, s1 in enumerate(strs[:-2]): 
    for s2 in strs[i+1:]: 
        for j in range(1, min(len(s1), len(s2))+1): 
            if s1[:j] == s2[:j]: 
                if j > max_cnt: 
                    max_cnt = j 
                    common = s1[:j] 

This function takes any number of positional arguments. If no argument is given, it returns "". If just one argument is given, it is returned.

from itertools import zip_longest

def common_prefix(*strings) -> str:
    length = len(strings)
    if not length:
        return ""
    if length == 1:
        return strings[0]
    # as pointed in another answer, 'key=len' is necessary because otherwise
    # the strings will be compared according to lexicographical order,
    # instead of their length
    shortest = min(strings, key=len)
    longest = max(strings, key=len)
    # we use zip_longest instead of zip because `shortest` might be a substring
    # of the longest; that is, the longest common prefix might be `shortest`
    # itself
    for i, chars in enumerate(zip_longest(shortest, longest)):
        if chars[0] != chars[1]:
            return shortest[:i]
    # if it didn't return by now, the first character is already different,
    # so the longest common prefix is empty
    return ""


if __name__ == "__main__":
    for args in [
        ("amigo", "amiga", "amizade"),
        tuple(),
        ("teste",),
        ("amigo", "amiga", "amizade", "atm"),
    ]:
        print(*args, sep=", ", end=": ")
        print(common_prefix(*args))

Simple python code

def longestCommonPrefix(self, arr):
    
    arr.sort(reverse = False)
    print arr
    n= len(arr)
    str1 = arr[0]
    str2 = arr[n-1]
    
    n1 = len(str1)
    n2 = len(str2)
    result = ""
    j = 0
    i = 0
    
    while(i <= n1 - 1 and j <= n2 - 1):
        if (str1[i] != str2[j]):
            break
        result += (str1[i])

        i += 1
        j += 1

    return (result)
Related