我们给出了两个小写拉丁字母字母序列.它们的长度相同,并且具有相同数量的给定类型的字母(第一个具有与第二个相同数量的t,依此类推).我们需要找到将第一个序列转换为第二个序列所需的最小交换次数(通过"交换",我们的意思是改变两个相邻字母的顺序).我们可以安全地假设每两个序列可以相互转换.我们可以用蛮力做到这一点,但序列太长了.
输入:
序列的长度(至少2,最多999999),然后是两个序列.输出:
一个整数,表示序列变为相同所需的交换数.示例:
{5,aaaaa,aaaaa}应输出{0},
{4,abcd,acdb}应输出{2}.
我想到的第一件事是bubblesort.我们可以简单地对每个交换的序列进行计数.问题是:a)它是O(n ^ 2)最坏情况b)我不相信它会给我每个案例的最小数字......即使是优化的bubblesort似乎也没有做到这一点.我们可以实施鸡尾酒种类来解决海龟的问题 - 但它会给我最好的表现吗？或者也许有更简单/更快的东西？
这个问题也可以表述为:当允许的唯一操作是换位时,我们如何确定两个字符串之间的编辑距离？
algorithm ×1