Java 两有序列表内的差异节点的个数

[matepi]

已知列表有序、内部节点可重复

AA
AA
差异=0

AA
AB
差异=1

AAA
ACA
差异=1

AA
ACA
差异=1 （一个缺少，但后续的要继续同步比较）

AABBCC
ABDCE
差异=3

这样的定义、尤其是在节点可重复时是否会有结果不确定性？
该用什么样的算法？
在 Java 里面已实现的轮子有吗？

[chendy]

最…最小编辑距离？
commons-text 里可能有现成的吧

[xxdd]

先 sort
然后 LCS

[matepi]

@chendy 恩，应该类似的了。不过问题可能表达的不太好，这里的 A，不是简单的文字 A，而是一个具体对象、或者说具体这个对象的 hash

[matepi]

@xxdd sort 会损失有序性

[xxdd]

那就 LCS 就好了 长度减一下

[ffbh]

差异节点个数是怎么定义的？
比如
ABC
ACB
差异=？

[matepi]

@ffbh 差异=2，因为有序

[ffbh]

我还是不明白这个差异个数是怎么计算的，能给出详细的定义么
比如这个
AABBCC
ABDCE
差异=3
为啥是 3

[ffbh]

综合这么多测试例子，我唯一得出的结论
差异个数=min(删除两个字符串字母的个数使得两个字符串长度相等 + 删除后两个字符串不相同位的数量)

[Sunyanzi]

@ffbh 关键字 Levenshtein distance ... 我觉得这么常见的算法肯定有现成的轮子 ...

[ffbh]

@Sunyanzi
是有点像这个，但是楼主也没给出具体的定义呀

[matepi]

@Sunyanzi
@ffbh
是的，就是 editing distance 或者说 Levenshtein distance，commons-text 有轮子
但问题是是针对文字 character 的，没有对于对象或者 word 适用的轮子

[ffbh]

@matepi
你把==改成 equals 不可以么

[matepi]

@ffbh 也可以考虑，但比造轮子更难过的事情，就是改别人的轮子啊
先凑活着放了个不考虑有序性的上去跑着了

[BiteTheDust]

看你这描述就是求一个最长公共子列 作为两列表的相同部分？

[srlp]

既然明确明确是 edit distance 了，那么网上搜搜针对 String 的源代码，改为 List<Object> 就可以了