将两个字符串合并为一个

Question

假设我有两个字符串

AAABBBCCCCC

和

AAAABBBBCCCC

为了尽可能使这些字符串相似，假设我只能删除一些字符，请按照以下方式进行操作：

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

这样它们就会变成：

AAABBBCCCC

如何高效地找出需要从每个字符串中删除的字符？

我正在思考一种解决方案，涉及到子字符串，并在另一个字符串中查找它们。

- bigblind

---

需要注意删除字符的顺序吗？例如，您是否需要知道要删除的是第4个A和最后一个C，还是只需要知道有一个A和一个C需要被删除？ - Nadh

如果要删除的字符的顺序无关紧要，那么将两个字符串排序并从较大的字符串中减去较小的字符串是否可行？ - Nadh

在编程中，对于相同字符组内的顺序并不重要。例如，在字符串“ÀABBAA”中，删除第一个字符与删除第二个字符是相同的，但删除第一个字符与删除最后一个字符是不同的。 - bigblind

好的Python模块用于模糊字符串比较 - georg

要得到通用解决方案，您需要找到最长公共子序列，这是一个非常适合用动态规划解决的好问题 :) - Niklas B.

Answer 1

Levenshtein距离可以计算将一个字符串转换为另一个字符串所需进行的更改数量。对源字符串稍作修改，您可以得到不仅距离，还有所需的转换。

- lenik

---

Levenshtein算法还允许修改单个字符，而这在OP的描述中是不允许的。 - Niklas B.

使用Levenshtein算法作为基础，您可以引入或删除任何您喜欢或不喜欢的字符修改。 - lenik

是的，但这样可能会导致您无法找到最佳的移除次数。 - Niklas B.

Levenstein处理1）删除字符2）添加字符3）替换字符，第一个意味着“从第一个字符串中删除字符”，第二个意味着“从第二个字符串中删除字符”，第三个意味着“从两个字符串中删除字符”。如果需要进一步澄清，请开设单独的问题。 - lenik

我刚刚意识到算法可以配置为将不同的操作分配不同的成本。在我们的情况下，我们需要将“字符替换”指定为2的成本。 - Niklas B.

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

- daedalus

---

因此，使用这个解决方案会像这样：''.join(s[2] for s in difflib.ndiff(s1,s2) if s[0] == ' ')。 - jamylak

如果删除额外字符会触发其他操作，那么较长的版本可能有用。+1 以简明的方式进行重述。 - daedalus

Answer 3

不知道它是否是最快的，但是就代码而言，至少它很短：

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

- deinonychusaur

Answer 4

我认为正则表达式可以解决这个问题。这是一个字符串距离问题。 我的意思是，我们有两个字符串：

str1 = 'abc'
str2 = 'aabbcc'

首先，我选择了短语，并构建了一个正则表达式，如下所示：

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

然后，我们可以搜索：

matches = re.search(regex,str2)

我使用圆括号来分组我感兴趣的部分。这些匹配组的matches.group()是两个字符串之间的距离。接下来，我可以确定应该删除哪些字符。这是我的想法，希望能对你有所帮助。

- hakunami