facendo due stringhe in un unico

Diciamo che ho 2 stringhefacendo due stringhe in un unico

AAABBBCCCCC

AAAABBBBCCCC

per rendere queste stringhe il più possibile simili, visto che posso rimuovere solo i caratteri che dovrei

eliminare l'ultimo C dalla prima stringa
eliminare l'ultimo A e l'ultimo B dalla seconda corda,

in modo che diventino

AAABBBCCCC

quello che sarebbe un algoritmo efficiente per scoprire quali caratteri da rimuovere da ogni stringa?

Attualmente sto schiacciando le mie cellule cerebrali pensando a una solluzione che coinvolge sottostringhe delle stringhe, cercandole io e l'altra stringa.

fonte

2012-05-06 bigblind

L'ordine dei caratteri da rimuovere è importante? Ad esempio, devi sapere che è il 4 ° A e l'ultimo C che devono essere rimossi, o hai solo bisogno di sapere che c'è un A e un C da rimuovere? – Nadh

Se l'ordine dei caratteri da rimuovere non ha importanza, non ordinerebbe entrambe le stringhe e sottraendo quella più piccola dal lavoro più grande? – Nadh

l'ordine non ha importanza all'interno di gruppi dello stesso gruppo degli stessi caratteri, ad esempio nella stringa 'ÀABBAA' la rimozione del primo carattere equivale a rimuovere il secondo, ma la rimozione del primo carattere non equivale alla rimozione l'ultimo. – bigblind

Levenshtein distance può calcolare quante modifiche è necessario convertire una stringa in un'altra. Una piccola modifica alla fonte e potresti ottenere non solo la distanza, ma le conversioni necessarie.

fonte

2012-05-06 11:05:09 lenik

Levenshtein consente anche modifiche di singoli caratteri, cosa non consentita dalla descrizione dell'OP. –

usando levehshtein come base, puoi introdurre o rimuovere qualsiasi modifica di carattere che ti piace o non ti piace. – lenik

Sì, ma potrebbe darsi che non si trovi il numero ottimale di rimozioni. –

Non so se è il più veloce, ma come codice va, è almeno breve:

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

fonte

2012-05-06 11:06:13 deinonychusaur

Come sull'utilizzo 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'

Questo stamperà le differenze tra le due stringhe che è possibile utilizzare per rimuovere le differenze. Ecco l'output:

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

fonte

2012-05-06 11:06:51 gauden

Così usando la soluzione sarebbe qualcosa come questo '' '.join (s [2] per s in difflib.ndiff (s1, s2) if s [0] ==' ') ' – jamylak

+1 per riformulazione concisa. La versione più lunga potrebbe essere utile se la rimozione dei caratteri extra dovesse attivare anche altre azioni. – gauden

Penso che l'espressione regolare possa farlo. È un problema di distanza stringa. Intendo. Diamo due stringa:

str1 = 'abc' 
str2 = 'aabbcc'

prima, ho scelto il breve, e costruire un'espressione regolare come è:

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

Poi, possiamo cercare:

matches = re.search(regex,str2)

Io uso rotonda parentesi per raggruppare la sezione che mi interessa. questi gruppi di matches.group() è la distanza di due stringhe. Successivamente, posso capire quali caratteri devono essere rimossi. È una mia idea, spero possa aiutarti.

fonte

2012-05-06 11:08:12 hakunami

facendo due stringhe in un unico

risposta

Problemi correlati