c++ - 之字形字符串的最小编辑距离

Question

我有这样的字符串 xxoxxooo，我想将其编辑为这种形式 xoxoxoxo，我的问题是如何找到最小数量的交换，我只能交换 2 个邻居作为交换。我考虑过遍历字符串并找到最近的冗余 x 并将其移动到当前位置，但我认为这太慢了，因为字符串可以有 1e6 * 2 个字符。有任何想法吗？

Answer 1

让我们表示位置和s_i之间的交换ii+1

假设您有一个S = s_{i1} s_{i2} ...从A到的最小交换序列B。因为它是最小的，所以您只能x与o而不是x与 anx或 ano与 an交换o。因此， 的动作S是将第一个 发送到第o一个A，o将B第二个o发送A到第二个o，B依此类推。因此，swap 的数量不能小于

Sum_i abs(pos of i-st o in A - pos of i-st o in B)

现在很容易找到恰好具有这个交换次数的序列，因此这是正确的值。

这是一个计算它的算法

Input: s1 and s2 of common length n
I'm assuming that they contains the same number of 'x' and 'o'

res = 0;
i1 = 0; i2 = 0;
while true do
    // find the next o
    while i1 < n and s1[i1] == 'x' do
        i1++
    if i1 == n return res
    // no check that i2 < n because of assumption
    while s2[i2] == 'x' do 
        i2++
    res += abs(i1-i2)
    i1++; i2++

Answer 2

您可以忽略其中一种类型的字符，并计算每个其他类型的字符到每个目标位置的距离。

更具体地说，所选类型字符的第 i 次出现将始终映射到第 i 个目标位置 - 将其移过该点将是多余的（因为我们将在某些时候交换两个相同类型点），如果它没有移到那里，那么一侧的那种类型的字符就不够了。此外，由于我们只能交换相邻的字符，因此我们采取的移动次数正好等于将字符移到某个位置的距离。

这可以通过以下算法完成：（伪代码）

distance = 0
pos = 0
for i = 0 to n
  if i == 'x'                     // only check 'x's
    distance += abs(i - pos)      // calculate distance to target position
    pos += 2                      // move to the next position

对于您的示例：

index      0 1 2 3 4 5 6 7
character  x x o x x o o o
distance 0 0 1 1 2 4 4 4 4
pos      0 2 4 4 6 8 8 8 8

所以距离是4。