Как найти слова в матрице букв

Ответ 1

Как насчет:

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

Я не думаю, что хэш был бы очень полезной оптимизацией здесь.

Ответ 2

Наиболее подходящее решение сильно зависит от ограничений, с которыми вы рассчитываете иметь дело. Насколько велик ваш словарь? Насколько велико ваш кроссворд.

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

Конструкция дерева - O (N) и потребляет пространство O (N), где N - размер вашего словаря в символах. Затем поиск займет время O (PQ), где кроссворд имеет размер PxQ. Предоставление общего времени выполнения O (N + PQ) и пространства O (N).

Дело в том, что суффиксные деревья - это боль для реализации. Они на самом деле. Таким образом, вы можете предпочесть простую настройку Trie, которая даст вам общее время выполнения O (N + PQ (max (P, Q )).

Ответ 3

Этот вопрос точно так же будет играть Boggle.

Этот предыдущий вопрос в SO более чем достаточно ОТВЕТИТ ЭТОТ ВОПРОС.

Удачи...

Ответ 4

Предположим, что словарь содержит n слов средней длины k, а матрица содержит знаки m2.

• Препроцессор словарь в префиксное дерево (aka trie). - O (kn)
• Для каждой позиции в матрице найдите строки в инете. - O (м³)

Общее время: O (max (kn, m³))

В реалистичных поисковых словах средняя длина слов, найденных в матрице, больше похожа на k, чем на m, поэтому время будет O (k max (n, м²)).

Ответ 5

Что случилось с вашим ответом?

• Словарь отсортирован, поэтому я считаю, что словаря слова будут переведены в префикс . Это поможет, так как есть много слов, где префикс также является словом. Сортировка помогает (минимально) со временем сборки.

• Затем пройдите кроссворд, глядя на все возможные слова. Когда вы извлекаете символы потенциального слова, вы идете по три - так что вы найдете первое слово, начинающееся с определенного набора символов, но также и в нужном месте, чтобы продолжать находить другие слова, начинающиеся с того же символы

Ответ 6

Я бы скомпилировал словарь в DFA, который распознавал слова в словаре, а затем запускал его по строкам и столбцам и диагоналям буквенной матрицы. Должно быть O(m+n), где m - длина словаря в символах, а n - площадь (w * h) матрицы.