这是一个创建于 2114 天前的主题，其中的信息可能已经有所发展或是发生改变。
已知列表有序、内部节点可重复
AA
AA
差异=0
AA
AB
差异=1
AAA
ACA
差异=1
AA
ACA
差异=1 （一个缺少，但后续的要继续同步比较）
AABBCC
ABDCE
差异=3
这样的定义、尤其是在节点可重复时是否会有结果不确定性？
该用什么样的算法？
在 Java 里面已实现的轮子有吗？
AA
AA
差异=0
AA
AB
差异=1
AAA
ACA
差异=1
AA
ACA
差异=1 （一个缺少，但后续的要继续同步比较）
AABBCC
ABDCE
差异=3
这样的定义、尤其是在节点可重复时是否会有结果不确定性？
该用什么样的算法？
在 Java 里面已实现的轮子有吗？
 | 1 chendy 2019-12-31 14:32:28 +08:00 最…最小编辑距离？ commons-text 里可能有现成的吧 |
 | 2 xxdd 2019-12-31 14:46:47 +08:00 先 sort 然后 LCS |
 | 3 matepi OP @chendy 恩，应该类似的了。不过问题可能表达的不太好，这里的 A，不是简单的文字 A，而是一个具体对象、或者说具体这个对象的 hash |
| 5 xxdd 2019-12-31 15:01:04 +08:00 那就 LCS 就好了 长度减一下 |
 | 6 ffbh 2019-12-31 17:28:08 +08:00 差异节点个数是怎么定义的？ 比如 ABC ACB 差异=？ |
| 8 ffbh 2019-12-31 17:36:03 +08:00 我还是不明白这个差异个数是怎么计算的，能给出详细的定义么 比如这个 AABBCC ABDCE 差异=3 为啥是 3 |
| 9 ffbh 2019-12-31 17:40:24 +08:00 综合这么多测试例子，我唯一得出的结论 差异个数=min(删除两个字符串字母的个数使得两个字符串长度相等 + 删除后两个字符串不相同位的数量) |
| 12 matepi OP |
| 14 matepi OP @ffbh 也可以考虑，但比造轮子更难过的事情，就是改别人的轮子啊 先凑活着放了个不考虑有序性的上去跑着了 |
 | 15 BiteTheDust 2020-01-01 12:07:15 +08:00 看你这描述就是求一个最长公共子列 作为两列表的相同部分？ |
 | 16 srlp 2020-01-01 13:48:40 +08:00 via iPhone 既然明确明确是 edit distance 了，那么网上搜搜针对 String 的源代码，改为 List<Object> 就可以了 |
Select Language