Доброго времени суток. Есть такая задача. Есть слово А и слово Б, можно удалить или добавить букву в А. Нужно определить можно ли двумя такими операциями из А делать Б. То есть из слова "Кто" можно сделать "Кот" (убрать букву "т" и поставить букву "т" в конец) 

В голову пришло только

1) проверить на количество букв, если разница больше, чем один символ, то нельзя.
2) проверить пересечение букв, если разница больше, чем в одну букву, то нельзя.
3) сделать из слов два набора (уникальных множества) букв, пройтись по набору и узнать количество несоответствий.

Но мне кажется, должен быть путь короче =)) Спасибо.

Ну количества букв - это хорошее отсечение, но, так или иначе, решение должно сводиться к сравнению строк: одни только количества букв не говорят о равенстве строк.


Достаточно быстрое решение может быть таким: сгенерируем два множества: множество всех слов, которые можно получить из А, и множество всех слов, которые можно получить из Б. Если у этих двух множеств есть общий элемент - то ответ ДА, иначе - НЕТ.


Если говорить о скорости решения (хотя автор не озвучил никаких ограничений на длину слов), то прямо в таком "наивном" виде оно имеет асимптотику O (n^2 log n) - если явным образом строить всевозможные строки и сортировать их. (где n - длина строк)
Т.е. для строк длины порядка 1000 это решение сгодится.


Впрочем, это решение нетрудно довести до оптимального времени O(n) в среднем, воспользовавшись техникой хеширования:
1) строки будем хешировать обычным полиномиальным хешом:

где A[i] - это код i-го символа строки А, p - некоторое небольшое число, q - некоторое большое число.
2) легко научиться считать за O(1) хеш от строки, полученной вставкой в какую-либо позицию какого-либо символа (для этого достаточно только предпосчитать HASH от всех префиксов и суффиксов строки A)
3) построив за O(n) два множества хешей, нам надо проверить, есть ли в них совпадающие элементы. Для этого можно воспользоваться структурой данных hash-set, которая обеспечивает нам O(1) в среднем на одну операцию, что и даст нам итоговые O(n).

Спасибо огромное.

Это сообщение отредактировал(а) xTr1m - 11.12.2011, 13:14