Выражение произвольной перестановки в виде последовательности операций (вставка, перемещение, удаление)

9

Предположим, у меня есть две строки. Назовите их и . Ни одна строка не имеет повторяющихся символов.AB

Как найти самую короткую последовательность операций вставки, перемещения и удаления, которая превращает в , где:AB

  • insert(char, offset)вставляет charв заданную offsetстроку
  • move(from_offset, to_offset)перемещает символ в настоящее время со смещением from_offsetв новую позицию, чтобы он имел смещениеto_offset
  • delete(offset) удаляет символ в offset

Пример приложения: вы делаете запрос к базе данных и показывает результаты на своем веб-сайте. Позже вы повторно запустите запрос к базе данных и обнаружите, что результаты изменились. Вы хотите изменить то, что на странице, чтобы соответствовать тому, что в настоящее время находится в базе данных, используя минимальное количество операций DOM. Есть две причины, по которым вы хотите самую короткую последовательность операций. Во-первых, эффективность. Когда изменяется только несколько записей, вы должны убедиться, что вы выполняете а не DOM-операций, поскольку они дороги. Во-вторых, правильность. Если элемент перемещался из одной позиции в другую, вы хотите переместить связанные узлы DOM за одну операцию, не уничтожая и не воссоздавая их. В противном случае вы потеряете состояние фокуса, содержание элементов и так далее.O(1)O(n)<input>

Geoff
источник

Ответы:

10

Я предлагаю взглянуть на алгоритм редактирования расстояния . Вместо того, чтобы просто рассчитать расстояние, вы захотите записать свой минимальный весовой путь через массив и вернуть его.

Рик Минерих
источник
5
На самом деле, поскольку повторений нет, это немного более простая проблема, называемая проблемой расстояния Улама. Хотя вы можете использовать алгоритм редактирования расстояния, существуют и более быстрые методы, нацеленные на это расстояние: mit.edu/~andoni/papers/ulamSublinear.pdf
Suresh
1
Дистанция редактирования обычно не охватывает moveоперации, поэтому вам может потребоваться измениться при интерпретации оценки.
Рафаэль