haciendo dos cadenas en una

Digamos que tengo 2 cuerdashaciendo dos cadenas en una

AAABBBCCCCC

AAAABBBBCCCC

para hacer estas cadenas tan similares como sea posible, teniendo en cuenta que sólo puedo eliminar los caracteres que debería

borrar la última C de la primera cadena
borrar la última A y el último B de la segunda cadena,

para que se conviertan

AAABBBCCCC

lo que sería un algoritmo eficiente para saber qué caracteres de eliminar de cada cadena?

Actualmente estoy aplastando mis células cerebrales pensando en una solución que implica subcadenas de las cuerdas, buscándolas en la otra cuerda.

Fuente

2012-05-06 bigblind

¿Importa el orden de los caracteres a eliminar? Por ejemplo, ¿tiene que saber que es la 4ta A y la última C las que deben eliminarse, o solo necesita saber que hay una A y una C que deben eliminarse? – Nadh

Si el orden de los caracteres a eliminar no importa, ¿no ordenaría ambas cadenas y restaría la más pequeña del trabajo más grande? – Nadh

el orden no importa dentro de grupos del mismo grupo de los mismos caracteres, por ejemplo, en la cadena 'ÀABBAA' eliminar el primer carácter sería lo mismo que eliminar el segundo, pero eliminar el primer carácter no es lo mismo que eliminar el último. – bigblind

Levenshtein distance puede calcular cuántos cambios necesita para convertir una cadena en otra. Un pequeño cambio en la fuente, y puede obtener no solo la distancia sino las conversiones necesarias.

Fuente

2012-05-06 11:05:09 lenik

Levenshtein también permite modificaciones de caracteres individuales, lo que no está permitido por la descripción de OP. –

usando levehshtein como base, puede introducir o eliminar cualquier modificación de carácter que le guste o no le guste. – lenik

Sí, pero puede ser que no encuentre el número óptimo de eliminaciones. –

No sabe si es el más rápido, pero a medida que va el código, que es por lo menos a corto:

import difflib 
''.join([c[-1] for c in difflib.Differ().compare('AAABBBCCCCC','AAAABBBBCCCC') if c[0] == ' '])

Fuente

2012-05-06 11:06:13 deinonychusaur

Cómo sobre el uso difflib?

import difflib 

s1 = 'AAABBBCCCCC' 
s2 = 'AAAABBBBCCCC' 

for difference in difflib.ndiff(s1, s2): 
    print difference, 
    if difference[0] == '+': 
     print 'remove this char from s2' 
    elif difference[0] == '-': 
     print 'remove this char from s1' 
    else: 
     print 'no change here'

Esto imprimirá las diferencias entre las dos cadenas que puede utilizar para eliminar las diferencias. Aquí está la salida:

A no change here 
    A no change here 
    A no change here 
+ A remove this char from s2 
+ B remove this char from s2 
    B no change here 
    B no change here 
    B no change here 
    C no change here 
    C no change here 
    C no change here 
    C no change here 
- C remove this char from s1

Fuente

2012-05-06 11:06:51 gauden

Utilizando esto, la solución sería algo así como ''' .join (s [2] para s en difflib.ndiff (s1, s2) si s [0] == '')' – jamylak

+1 para una reformulación concisa. La versión más larga puede ser útil si la eliminación de los caracteres adicionales también debe desencadenar otras acciones. – gauden

Creo expresión regular puede hacer this.It es un problema de la distancia cadena. Es decir. Vamos a tener dos cuerdas:

str1 = 'abc' 
str2 = 'aabbcc'

principio, elegir el corto, y construir una expresión regular como es:

regex = '(\w*)'+'(\w*)'.join(list(str1))+'(\w*)'

Entonces, podemos buscar:

matches = re.search(regex,str2)

utilizo ronda corchetes para agrupar la sección Estoy interesado. estos grupos de matches.group() es la distancia de dos cadenas. Luego, puedo averiguar qué caracteres deben eliminarse. Es mi idea, espero que pueda ayudarte.

Fuente

2012-05-06 11:08:12 hakunami

Respuesta

Cuestiones relacionadas