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

Ответ 1

Никогда не переписывайте то, что вам предоставляется: os.path.commonprefix делает именно это:

Возвращает самый длинный префикс пути (принято по-символу), который является префиксом всех путей в списке. Если список пусто, верните пустую строку (''). Обратите внимание, что это может вернуться неверные пути, потому что он работает с символом за раз.

Для сравнения с другими ответами, здесь код:

# Return the longest prefix of all list elements.
def commonprefix(m):
    "Given a list of pathnames, returns the longest common leading component"
    if not m: return ''
    s1 = min(m)
    s2 = max(m)
    for i, c in enumerate(s1):
        if c != s2[i]:
            return s1[:i]
    return s1

Ответ 2

Ned Batchelder, вероятно, прав. Но для удовольствия, здесь более эффективная версия 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_'

Ответ 3

Здесь мое решение:

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]

Ответ 4

Ниже приведено рабочее, но, вероятно, довольно неэффективное решение.

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.

Ответ 5

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

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, что является довольно элегантной функцией.

Ответ 6

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

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

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

Ответ 7

Вот еще один способ сделать это с помощью 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)])

Ответ 8

Здесь простое чистое решение. Идея состоит в том, чтобы использовать функцию 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 _