Дуплеты Кэрролла
В марте 1879 года Льюис Кэрролл напечатал в журнале Vanity Fair новую игру — «дуплеты». Даны два слова одинаковой длины; превратите первое во второе, меняя за ход одну букву и оставляя её на своём месте, и каждое промежуточное слово должно быть настоящим словом. Его собственный пример: HEAD → HEAL → TEAL → TELL → TALL → TAIL. По-русски так же: день → тень → течь → точь → ночь.
Вам дан словарь и два слова из него. Найдите цепочку с наименьшим числом ходов. Один из тестов — все пятибуквенные слова «Войны и мира», и там от «пушки» до «ружья» девять ходов.
Вход
В первой строке число n — размер словаря (1 ≤ n ≤ 10 000). Во второй — начальное и конечное слово через пробел. Дальше n строк — слова словаря, все разные. Начальное и конечное слово есть в словаре. Все слова одной длины L (1 ≤ L ≤ 10) и состоят из строчных букв: в одних тестах латинских, в других русских (буква ё заменена на е). Вход в кодировке UTF-8; в Go сравнивайте руны, а не байты.
Выход
Если превратить одно слово в другое нельзя, выведите -1. Иначе в первой строке — наименьшее число ходов k, во второй — цепочку из k + 1 слова через пробел, от начального до конечного. Если кратчайших цепочек несколько, подойдёт любая.
Примеры
Пример 1
21 head tail tale belt read bead seal load lead road toll teal tail tell heal head heat bell meal toil tall beat held
5 head heal teal tell tall tail
Пример 2
10 cold warm card cord wart warm bold core cold bolt word wore
-1
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Слова — вершины графа, ход — ребро. Какой обход находит путь с наименьшим числом рёбер?
2Подсказка 2
Граф можно построить, сравнив каждую пару слов. Сколько это сравнений при десяти тысячах слов? А сколько соседей у слова на самом деле может быть, если оно длины L?
3Подсказка 3
Слова «head» и «heal» совпадают везде, кроме последней буквы. Если её закрыть звёздочкой, оба превратятся в одну и ту же строку «hea*».
4Идея
Нужен обычный обход в ширину от начального слова: первый раз, когда волна дошла до конечного слова, это и есть кратчайшая цепочка, а родители восстанавливают её задом наперёд. Вся трудность — в соседях. Для каждого слова и каждой позиции заведём ключ: слово, в котором эта буква заменена на *. Все слова с одинаковым ключом попарно отличаются ровно одной буквой — это и есть рёбра, и собираются они одним проходом по словарю.
5Разбор
Сначала раскладываем слова по «корзинам»: buckets["hea*"] = [head, heal, heat]. Потом обход в ширину: у слова u соседи — все слова в его L корзинах, кроме него самого. Каждую корзину достаточно открыть один раз: слова в ней — соседи друг друга, и тот, кто открыл корзину первым, ближе всех к старту, поэтому все её слова получают правильное расстояние сразу. Эталон удаляет корзину после первого открытия.
Есть и второй способ найти соседей: перебрать все замены каждой буквы на каждую букву алфавита и проверить, есть ли получившееся слово в множестве. Это L · 33 проверки на слово вместо n сравнений — тоже быстро.
Почему ответ кратчайший, разобрано в статье: волна обходит слова по слоям, и слово впервые видят с наименьшим возможным числом ходов.
5+Решение
6Сложность
Корзин не больше nL, каждое слово лежит в L корзинах, ключ строится за O(L): всего O(nL²) времени и памяти. Сравнение всех пар стоит O(n²L): при n = 10 000 это пятьдесят миллионов пар слов, и на Python такой перебор идёт минуты.
7Типичные ошибки
- Все пары слов. Ответ правильный, но на словаре из десяти тысяч слов не уложиться во время: это и есть
wrong.py. - Поиск в глубину. Находит цепочку, но не самую короткую: от «мать» до «отец» в словаре «Войны и мира» он легко уйдёт на сотни ходов вместо девятнадцати.
- Байты вместо букв. В UTF-8 русская буква занимает два байта. Если сравнивать байты, слова, которые отличаются одной русской буквой, часто отличаются в двух байтах подряд, и такой ход не засчитается. В Go переводите слово в
[]rune. - Начало совпадает с концом. Ответ 0 и цепочка из одного слова.