Determinar el prefijo común de varias cadenas

Tengo un conjunto de cuerdas, por ejemplo

my_prefix_what_ever
my_prefix_what_so_ever
my_prefix_doesnt_matter

Simplemente quiero encontrar la porción común más larga de estas cadenas, aquí el prefijo. En lo anterior el resultado debe ser

my_prefix_

Las cuerdas

my_prefix_what_ever
my_prefix_what_so_ever
my_doesnt_matter

debe dar como resultado el prefijo

my_

¿Existe una forma relativamente indolora en Python para determinar el prefijo (sin tener que iterar sobre cada carácter manualmente)?

PD: estoy usando Python 2.6.3.

Nunca reescriba lo que se le proporciona: os.path.commonprefix hace exactamente esto:

Devuelve el prefijo de la ruta más larga (tomado carácter por carácter) que es un prefijo de todas las rutas de la lista. Si la lista está vacía, devuelve la cadena vacía (''). Tenga en cuenta que esto puede devolver rutas no válidas porque funciona con un carácter a la vez.

Para comparar con las otras respuestas, aquí está el código:

# 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

Ned Batchelder probablemente tenga razón. Pero por diversión, aquí hay una versión más eficiente de la respuesta de phimuemue usando 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)

Como una afrenta a la legibilidad, aquí hay una versión de una línea 🙂

>>> 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_'

Aquí está mi solución:

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]

La siguiente es una solución funcional, pero probablemente bastante ineficiente.

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)

Para pequeños conjuntos de cuerdas, lo anterior no es ningún problema. Pero para conjuntos más grandes, personalmente codificaría otra solución manual que verifique cada carácter uno tras otro y se detenga cuando haya diferencias.

Algorítmicamente, esto produce el mismo procedimiento, sin embargo, uno podría evitar construir la lista c.

Solo por curiosidad, descubrí otra forma de hacer esto:

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_"

Como Ned señaló, probablemente sea mejor usar os.path.commonprefixque es una función bastante elegante.

La segunda línea de esto emplea la función de reducción en cada carácter de las cadenas de entrada. Devuelve una lista de N+1 elementos donde N es la longitud de la cadena de entrada más corta.

Cada elemento en lote es (a) el carácter de entrada, si todo las cadenas de entrada coinciden en esa posición, o (b) Ninguna. lote.index(Ninguno) es la posición del primero Ninguno en lote: la longitud del prefijo común. afuera es ese prefijo común.

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

Aquí hay una solución simple y limpia. La idea es usar la función zip() para alinear todos los caracteres colocándolos en una lista de primeros caracteres, lista de segundos caracteres,… lista de caracteres n. Luego itere cada lista para verificar si contienen solo 1 valor.

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

salida: mi_prefijo_