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