строковый алгоритм перемещения
Предположим там дан две Строки:
String s1= "MARTHA"
String s2= "MARHTA"
здесь мы обмениваемся положениями T и H. Мне интересно писать код, который рассчитывает, сколько изменения необходимы для преобразования от одной Строки до другой Строки.
3 ответа
Предполагая, что расстояние учитывается только перестановками, вот идея, основанная на перестановках , который работает в линейном времени.
Первый шаг алгоритма - убедиться, что две строки действительно эквивалентны по своему содержанию символов. Это можно сделать за линейное время, используя хеш-таблицу (или фиксированный массив, покрывающий весь алфавит). Если это не так, то s2 не может считаться перестановкой s1, и «счетчик свопов» не имеет значения.
На втором этапе подсчитывается минимальное количество перестановок, необходимых для преобразования s2 в s1. Это можно сделать, проверив перестановку p, которая соответствует преобразованию из s1 в s2.Например, если s1 = "abcde" и s2 = "badce", то p = (2,1,4,3,5), что означает, что позиция 1 содержит элемент №2, позиция 2 - элемент №1 и т. Д. перестановка может быть разбита на циклов перестановки за линейное время. Циклы в примере - это (2,1) (4,3) и (5). Минимальное количество свопов - это общее количество свопов, требуемых за цикл. Цикл длины k требует k-1 перестановок, чтобы "исправить это". Следовательно, количество обменов равно N-C, где N - длина строки, а C - количество циклов. В нашем примере результат равен 2 (поменять местами 1,2, а затем 3,4).
Здесь есть две проблемы, и я думаю, что я слишком устал, чтобы решать их прямо сейчас:)
1) Мое решение предполагает, что ни один символ не повторяется, что не всегда так. Для правильного расчета количества свопов необходима некоторая корректировка.
2) Моя формула # MinSwaps = N-C требует подтверждения ... Я не нашел ее в сети.
Ваша проблема не так проста, поскольку перед подсчетом свопов вы должны убедиться, что каждый своп уменьшает «расстояние» (в равенстве) между этими двумя строками. Затем на самом деле вы ищете счетчик, но вы должны искать наименьшее количество (или, по крайней мере, я полагаю), иначе существует бесконечное количество способов поменять местами строку для получения другой.
Сначала вы должны проверить, какие символы уже установлены, затем для каждого символа, который не указан, посмотрите, есть ли пара, которую можно поменять местами, чтобы уменьшить следующее расстояние между строками. Затем повторяйте, пока не закончите процесс.
Если вы не хотите делать это эффективно, а просто подсчитываете количество замен, используйте битовый массив, в котором у вас есть 1 для каждого удачно размещенного символа и 0 в противном случае . Вы закончите, когда каждый бит будет 1 .
Существует несколько алгоритмов дистанции редактирования , данная ссылка Wikipeida имеет ссылки на некоторые из них.