13

假设我有 2 个字符串

AAABBBCCCCC

和

AAAABBBBCCCC

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

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

使他们成为

AAABBBCCCC

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

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

4

4 回答 4

15

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

于 2012-05-06T11:05:09.107 回答
14

怎么用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
于 2012-05-06T11:06:51.337 回答
1

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

import difflib
''.join([c[-1] for c in difflib.Differ().compare('AAABBBCCCCC','AAAABBBBCCCC') if c[0] == ' '])
于 2012-05-06T11:06:13.740 回答
0

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

str1 = 'abc'
str2 = 'aabbcc'

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

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

然后，我们可以搜索：

matches = re.search(regex,str2)

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

于 2012-05-06T11:08:12.277 回答