Делая две строки в одну

Скажем, у меня есть 2 строки

AAABBBCCCCC

AAAABBBBCCCC

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

удалить последнюю C из первой строки
удалите последний A и последний B из второй строки,

чтобы они стали

AAABBBCCCC

Что было бы эффективным алгоритмом, чтобы выяснить, какие символы удалить из каждой строки?

В настоящее время я разбиваю свои мозговые клетки, думая о разрешении, включающем подстроки строк, ища их, и другую строку.

Ответ 1

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

Ответ 2

Как насчет использования 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'

Это приведет к распечатке различий между двумя строками, которые вы затем можете использовать для устранения различий. Вот результат:

  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

Ответ 3

Не знаю, быстрее ли это, но как идет код, он по крайней мере короткий:

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

Ответ 4

Я думаю, что регулярное выражение может это сделать. Это проблема с расстоянием строки. Я имею в виду. Пусть есть две строки:

str1 = 'abc'
str2 = 'aabbcc'

во-первых, я выбираю short и строю регулярное выражение, например:

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

Затем мы можем выполнить поиск:

matches = re.search(regex,str2)

Я использую круглые скобки для группировки интересующего раздела. эти группы матчей .group() - это расстояние от двух строк. Далее я могу выяснить, какие символы следует удалить. Это моя идея, я надеюсь, что это может вам помочь.