Python: определение префикса из набора (похожих) строк

Нэд Батчелдер Это, наверное, правильно. Но для удовольствия, вот более эффективная версия phimuemue ответ с помощью itertools.

import itertools

strings = ['my_prefix_what_ever', 
           'my_prefix_what_so_ever', 
           'my_prefix_doesnt_matter']

def all_same(x):
    return all(x[0] == y for y in x)

char_tuples = itertools.izip(*strings)
prefix_tuples = itertools.takewhile(all_same, char_tuples)
''.join(x[0] for x in prefix_tuples)

как оскорбление читаемости, вот однострочная версия :)

>>> from itertools import takewhile, izip
>>> ''.join(c[0] for c in takewhile(lambda x: all(x[0] == y for y in x), izip(*strings)))
'my_prefix_'

вот мое решение:

a = ["my_prefix_what_ever", "my_prefix_what_so_ever", "my_prefix_doesnt_matter"]

prefix_len = len(a[0])
for x in a[1 : ]:
    prefix_len = min(prefix_len, len(x))
    while not x.startswith(a[0][ : prefix_len]):
        prefix_len -= 1

prefix = a[0][ : prefix_len]

следующее является рабочим, но, вероятно, довольно неэффективным решением.

a = ["my_prefix_what_ever", "my_prefix_what_so_ever", "my_prefix_doesnt_matter"]
b = zip(*a)
c = [x[0] for x in b if x==(x[0],)*len(x)]
result = "".join(c)

для небольших наборов строк, это не проблема вообще. Но для больших наборов я лично кодировал бы другое, ручное решение, которое проверяет каждый символ один за другим и останавливается, когда есть различия.

алгоритмически, это дает ту же процедуру, однако, можно избежать построения списка c.

просто из любопытства я придумал еще один способ сделать это:

def common_prefix(strings):

    if len(strings) == 1:#rule out trivial case
        return strings[0]

    prefix = strings[0]

    for string in strings[1:]:
        while string[:len(prefix)] != prefix and prefix:
            prefix = prefix[:len(prefix)-1]
        if not prefix:
            break

    return prefix

strings = ["my_prefix_what_ever","my_prefix_what_so_ever","my_prefix_doesnt_matter"]

print common_prefix(strings)
#Prints "my_prefix_"

как Нед указал, вероятно, лучше использовать os.path.commonprefix, что является довольно элегантной функцией.

во второй строке используется функция reduce для каждого символа во входных строках. Он возвращает список из N+1 элементов, где N-длина самой короткой входной строки.

каждый элемент много либо (a) входной символ, если все входные строки совпадают в этой позиции, или (b) нет. много.индекс(Нет) - это позиция первого нет in lot: длина общего префикса. из is это общий префикс.

val = ["axc", "abc", "abc"]
lot = [reduce(lambda a, b: a if a == b else None, x) for x in zip(*val)] + [None]
out = val[0][:lot.index(None)]

вот еще один способ сделать это с помощью OrderedDict с минимальным кодом.

import collections
import itertools

def commonprefix(instrings):
    """ Common prefix of a list of input strings using OrderedDict """

    d = collections.OrderedDict()

    for instring in instrings:
        for idx,char in enumerate(instring):
            # Make sure index is added into key
            d[(char, idx)] = d.get((char,idx), 0) + 1

    # Return prefix of keys while value == length(instrings)
    return ''.join([k[0] for k in itertools.takewhile(lambda x: d[x] == len(instrings), d)])

вот простое чистое решение. Идея состоит в том, чтобы использовать функцию zip() для выравнивания всех символов, помещая их в список 1-х символов, список 2-х символов,...список из n символов. Затем повторите каждый список, чтобы проверить, содержат ли они только 1 значение.

a = ["my_prefix_what_ever", "my_prefix_what_so_ever", "my_prefix_doesnt_matter"]

list = [all(x[i] == x[i+1] for i in range(len(x)-1)) for x in zip(*a)]

print a[0][:list.index(0) if list.count(0) > 0 else len(list)]

выход: my_prefix_