将两个字符串合二为一

Question

假设我有2个字符串

AAABBBCCCCC

和

AAAABBBBCCCC

鉴于我只能删除我应该删除的字符,使这些字符串尽可能相似

• 从第一个字符串中删除最后一个C.
• 删除第二个字符串中的最后一个A和最后一个B,

这样他们就变成了

AAABBBCCCC

找出从每个字符串中删除哪些字符的有效算法是什么？

我正在粉碎我的脑细胞,想着涉及弦的子串的溶解,在另一个弦中寻找它们.

Answer 1

Levenshtein距离可以计算将一个字符串转换为另一个字符串所需的更改次数.对源进行一些小改动,您不仅可以获得距离,还可以获得所需的转换.

Answer 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