Как найти слова в таблице?

Question

Это упражнение по кодированию. Предположим, есть таблица букв и количество слов. Я должен найти положения слов в таблице. Слово может начинаться в любом месте таблицы и может быть ориентировано либо вертикально, либо горизонтально. (Можно предположить, что строка / столбец может содержать только одно слово).

Например:

table = xabcx
        xxxdx
        xxfex

words = ["abc", "edc", "fe"]

expected output is (0,1), (2,3), (2,2)

Простое решение состоит в том, чтобы перебрать все строки / столбцы и проверить, содержит ли каждая строка / столбец какое-либо из слов. Требуется O(number of columns * number of rows * number of words * word length). Есть ли лучшее решение? Может быть, мне следует предварительно обработать список слов, чтобы построить более эффективную структуру данных?

Answer 1

Вы можете использовать структуру данных Trie для хранения таблицы. Поиск слов очень прост, если у вас есть три.

Answer 2

Использование алгоритма сопоставления строк Aho-Corasick для каждого столбца / строки занимает только O (number of columns * number of rows + length of patterns + number of output matches).

Answer 3

Вот простой подход.

Вы ищете только точные совпадения, поэтому я думаю, что вы должны немедленно рассмотреть алгоритмы, основанные на хэше, а не на основе дерева.Сначала рассмотрим хэш-карту, которая связывает каждую букву алфавита с ее позициями в таблице.Теперь для каждого слова вы смотрите на первую букву, а затем просмотрите таблицу (влево, вправо, вверх, вниз), чтобы увидеть, существует ли целое слово.

Вы можете улучшить это, создав вместо этого хеш-карта для каждой двухбуквенной комбинации (всего 676 клавиш) для каждого направления (влево, вправо, вверх, вниз).Теперь вы начинаете с проверки первых двух букв вашего слова, и хэш-карта сразу же дает вам местоположения, где эти две буквы существуют.Теперь вы можете продолжать смотреть в таблице в этом направлении, чтобы увидеть, завершено ли слово.В качестве альтернативы - вы можете взять следующие две буквы слова и посмотреть, есть ли место для этой пары букв, которое находится рядом с первой парой букв и имеет то же направление.

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

Answer 4

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