Алгоритм поиска сетки в другом направлении

Question

Сегодня соратник задал мне вопрос.Учитывая сетку символов и список слов, нужно было бы найти каждое вхождение этого слова в сетке по горизонтали, вертикали и диагонали.

Решение, которое мы придумали, работает и делает свое дело, но яинтересно посмотреть, как тикают умы других людей.

Answer 1

Вставьте каждое слово в список в три или хеш-таблицу или в любой словарь.

Теперь, для каждой позиции в вашей сетке, идите горизонтально,вертикально и по диагонали и посмотреть, если вы получаете совпадения в словаре.Это должно дать вам O(N^3) сложность наихудшего случая, где N - это размер сетки.В противном случае это O(N^2*averageWordLength) Я думаю.