CODEWITHSUNDEEP
python
Sail
Sail

Reputation: 21

Find the longest common prefix string amongst a list of strings

I am using python and I have to write a function to find the longest common prefix string amongst a list of strings.
For example, the input argument is ["flower", "flow", "flight"], the output is "fl". If there is no common prefix among the input strings, the output is an empty string.

Upvotes: 2

Views: 1598

Answers (3)

Pierrick Rambaud
Pierrick Rambaud

Reputation: 2364

I am not fluent enough with Python specific keywords but I propose a 6 line long other option on top of @Mark answer.

Here I take the first item as the longest potential "prefix", then for each string I reduce it's length to the min potential and then search for the first carracter where they diverge. If none is found I use the complete list.

def common_prefix(strings):
    """ Find the longest string that is a prefix of all the strings."""
    prefix = strings[0]
    for s in strings:
        prefix = prefix[:min(len(s), len(prefix))]
        prefix = prefix[:next((i for i, v in enumerate(prefix) if v != s[i]), None)]
    return prefix

Upvotes: 0

Mark
Mark

Reputation: 92440

You can zip your strings together zip(*list_o_strings) which will give you tuples like ('f', 'f', 'f'). If you pass those to a set, the set will only have a single value when all letters the same. Just loop over that zip until you hit a set with a length greater than one.

def common_prefix(l):
    s = ''
    for c, *rest in  map(set, zip(*l)):
        if rest:  # rest will be empty of the set is shorter than 1
            return s
        s += c
    return s

common_prefix(["flower", "flow", "flight"])
# 'fl'

common_prefix(["flower", "flow", "flog"])
# 'flo'

common_prefix(["glower", "flow", "flight"])
# ''

common_prefix(["flow", "flow", "flow"])
# 'flow'

Upvotes: 3

Aaj Kaal
Aaj Kaal

Reputation: 1274

def get_prefix_str(str_list):
    # take first string as reference and compare each char with the corresponding char of the rest of strings
    prefix_str = ''
    len_smallest_str = min([len(str_mem) for str_mem in str_list])
    for i in range(len_smallest_str): 
        if len([0 for ind in range(1, len(str_list)) if str_list[0][i] != str_list[ind][i]]) > 0:
            break 
        prefix_str += str_list[0][i]
    return prefix_str

for str_list in [["flower", "flow", "flight"], ["lower", "low", "light"], ["ower", "ow", "ight"]]:
    print(str_list)
    prefix_str = get_prefix_str(str_list)
    print(f'Prefix is {prefix_str}')

Output:

['flower', 'flow', 'flight']
Prefix is fl
['lower', 'low', 'light']
Prefix is l
['ower', 'ow', 'ight']
Prefix is

Upvotes: 0

Related Questions