python - 将两个字符串合二为一

Question

假设我有 2 个字符串

AAABBBCCCCC

和

AAAABBBBCCCC

使这些字符串尽可能相似，因为我只能删除我应该删除的字符

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

使他们成为

AAABBBCCCC

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

我目前正在粉碎我的脑细胞，思考涉及字符串子字符串的解决方案，在另一个字符串中寻找它们。

Answer 1

Levenshtein distance可以计算将一个字符串转换为另一个字符串需要多少更改。对源稍作改动，您不仅可以获得距离，还可以获得所需的转换。

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

Answer 3

不知道它是否是最快的，但随着代码的运行，它至少很短：

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

Answer 4

我认为正则表达式可以做到这一点。这是一个字符串距离问题。我是说。让我们有两个字符串：

str1 = 'abc'
str2 = 'aabbcc'

首先，我选择short，并构造一个正则表达式，如：

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

然后，我们可以搜索：

matches = re.search(regex,str2)

我使用圆括号对我感兴趣的部分进行分组。这组matches.group()是两个字符串的距离。接下来，我可以弄清楚应该删除哪些字符。这是我的想法，希望对你有帮助。