Лучший способ решения Word Chain

Я пытаюсь решить проблему this в CodeEval.

В этой задаче мы предлагаем вам сыграть в известной игре "Word цепь", в которой игроки придумывают слова, которые начинаются с буквы что предыдущее слово закончилось. Задача состоит в том, чтобы определить максимальная длина цепочки, которая может быть создана из списка слов.

Пример:

Input:
soup,sugar,peas,rice
Ouput:
4

Объяснение: Мы можем сформировать цепочку из 4-х слов: "суп- > горох- > сахар- > рис".

Ограничения:

  • Длина списка слов находится в диапазоне [4, 35].
  • Слово в списке слов представлено случайной строчной строкой ascii с длиной [3, 7] букв.
  • В списке слов нет повторяющихся слов.

Моя попытка. Мой подход заключается в моделировании слов в виде графика, так что каждое слово на входах представляет собой node и существует (направленное) ребро между wordi и wordj, если последний символ слова я равен первому символу слова.

После этого я запускаю bfs из каждого node и вычисляя длину самого дальнего node из этого node. Конечным результатом является максимальное значение, возможное для всех узлов.

Но этот подход не дает мне полной оценки. Следовательно, мой вопрос заключается в том, как решить эту проблему правильно и эффективно?

3 ответа

См. решение, упомянутое здесь: Обнаружение, когда возможно умножение матрицы

Решение вашей проблемы почти одинаково. Создайте ориентированный граф таким образом, чтобы для каждой работы добавлялось ребро от первой буквы до последней буквы.

Затем найдите путь Эйлера (http://en.wikipedia.org/wiki/Euler_path) в этом графе.

EDIT: я вижу, что вы не уверены в использовании всех слов, и вам нужен самый длинный путь на графике (http://en.wikipedia.org/wiki/Longest_path_problem), Эта проблема NP-полная.


См. решение, упомянутое в цепочке слов в ядре ядра

Страница дает решение в Core Java, это следует за следующим процессом:

  • Загрузите элементы Словаря в память для заданной длины слова
  • Получить следующий подходящий список слов из памяти для данного слова

Существует другой подход с использованием каркаса Map/reduce hadoop, который подробно описан в цепочке слов используя map-reduce


Для моей репутации менее 50, поэтому я не могу сделать комментарий...

Если общее число слов меньше 20, мы можем решить, используя динамическое программирование и битмаску. делают dp [20] [1 < 20]. dp [i] [j] означает, что в данный момент вы находитесь в i, и вы посещаете битмаск j word.

Для числа больше 20, у меня все еще не очень хорошая идея. Может быть, нам нужно использовать какой-то случайный алгоритм, возможно....

Моя идея - использовать dfs и добавить некоторую оптимизацию, потому что 35 не слишком большой. Я думаю, этого достаточно, чтобы решить проблему.

licensed under cc by-sa 3.0 with attribution.