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

Question

Это еще один вопрос, который мне задали в телефонном интервью:

По заданному словарю и кроссворду (двумерная матрица символов) найдите все слова из словаря, которые можно найти в кроссворде.

Все, что я мог придумать, это хэшировать словарь, находить каждое возможное слово в кроссворде и искать в хэше.Я не мог оптимизировать все это.

Должен признать, что вопросы об интервью Microsoft жесткие: (

Пожалуйста, дайте мне строки для размышлений.

Answer 1

Как насчет:

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

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

Answer 2

Этот вопрос - как играть Boggle .

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

Веселись ...

Answer 3

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

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

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

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

Answer 4

Что не так с вашим ответом?

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

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

Answer 5

Предположим, словарь содержит n слова средней длины k , а матрица содержит m ² символов.

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

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

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

Answer 6

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