Минимальное расстояние редактирования строки зигзага

Question

Минимальное расстояние редактирования строки зигзага

У меня есть строка, подобная этой xxoxxooo, и я хочу отредактировать ее в этой форме xoxoxoxo, мой вопрос заключается в том, как найти минимальное количество свопов, и я могу поменять местами только 2 соседа как своп. Я думал о том, чтобы пройти строку и найти ближайший избыточный x и переместить его в текущее место, но это слишком медленно, я думаю, потому что строка beacuse может иметь 1e6 * 2 символа. Есть идеи?

1

algorithm c++edit-distance zigzag

Решение

Другие решения

Давайте обозначим s_i своп между позицией i а также i+1

Предположим, что у вас есть минимальные последовательности обмена S = s_{i1} s_{i2} ... собирается из A в B, Потому что это минимально вы только поменять x с o и никогда x с x или o с o, Поэтому действие S это отправить первым o из A к первому o из B, второй o из A ко второму o из B и так далее. Поэтому количество свопов не может быть меньше

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++

2

Источник

Accepted Answer

Вы можете просто проигнорировать один из типов символов и посчитать расстояние каждого другого типа символа до каждой целевой позиции.

Более конкретно, 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.

0