Самый быстрый алгоритм поиска слова в сетке поиска слов

Question

У меня было интервью для позиции разработчика программного обеспечения. Это было телефонное интервью. Был задан вопрос, и это меня прослушивало весь день

Интервьюер попросил меня придумать общий подход для поиска слова в сетке поиска слов. Для простоты нет необходимости беспокоиться о ограничениях памяти или искать по диагонали по сетке (слева направо и сверху вниз).

Лучшее, что я мог придумать было создать хэш-карту при запуске программы сетки (перед вызовом слово искать каждый раз) ... есть это создать хэш-карту характера =>строк, col индексы. Таким образом, вы можете выполнить начальное сканирование в O (1) раз. А затем оттуда в основном сканируют слева направо или сверху вниз.

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

Answer 1

Если память не является проблемой, и я могу препроцессировать данные, то я бы:

1. Сделать строковое представление сетки в строке-мажорных порядке. Это для поиска по горизонтали.
2. Сделайте строковое представление сетки в порядке столбцов, для поиска по вертикали.

Когда дано слово для поиска, я хотел бы использовать стандартный алгоритм поиска (KMP, Boyer-Moore и т.д.):

1. Искать слово в строке-мажорные строки.
2. Обратное слово и поиск в строке строки.
3. Поиск слова в строке столбца.
4. Обратное слово и поиск в строке столбца.

Это дает хороший баланс между простотой, использованием памяти и скоростью. Фактически, это мертво просто, потому что вам не нужно будет реализовывать алгоритм поиска. Просто используйте то, что предоставляется библиотекой времени выполнения.

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

Выполнение его на месте с помощью одного сканирования осложняется. Но вы можете выполнять горизонтальные поиски (т. Е. Слева направо и справа налево) достаточно легко в одном сканировании. И вертикальные поиски в одном сканировании. Вы просто искали бы две разные строки за один проход: слово и обратную версию слова.

Answer 2

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