Boggle с помощью Trie

Опубликовано: 12 Января, 2023

Дан словарь, метод поиска в словаре и доска M x N, где каждая ячейка имеет один символ. Найдите все возможные слова, которые могут быть образованы последовательностью смежных символов. Обратите внимание, что мы можем перейти к любому из 8 соседних символов, но слово не должно иметь несколько экземпляров одной и той же ячейки.
Пример:

Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};
       boggle[][]   = {{"G", "I", "Z"},
                       {"U", "E", "K"},
                       {"Q", "S", "E"}};

Output: Following words of the dictionary are present
         GEEKS
         QUIZ

Explanation:

Input: dictionary[] = {"GEEKS", "ABCFIHGDE"};
       boggle[][]   = {{"A", "B", "C"},
                       {"D", "E", "F"},
                       {"G", "H", "I"}};
Output: Following words of the dictionary are present
         ABCFIHGDE
Explanation:

Мы обсудили решение на основе Graph DFS в посте ниже.
Boggle (Найти все возможные слова в таблице символов) | Набор 1
Здесь мы обсуждаем решение на основе Trie, которое лучше, чем решение на основе DFS.
Данный словарь-словарь[] = {"GEEKS", "FOR", "QUIZ", "GO"}
1. Создайте пустое дерево и вставьте в него все слова данного словаря.

After insertion, Trie looks like(leaf nodes are in RED)
                       root
                    /       
                    G   F     Q
                 /  |   |     |
                O   E   O     U
                    |   |     |
                    E    R     I
                    |         |  
                    K         Z 
                    |   
                    S

2. После этого мы выбираем только те символы в boggle[][], которые являются дочерними элементами корня Trie.
Пусть выше мы выбираем 'G' boggle[0][0], 'Q' boggle[2][0] (они оба присутствуют в матрице boggle)
3. искать слово в дереве, которое начинается с символа, который мы выбрали на шаге 2

1) Create bool visited boolean matrix (Visited[M][N] = false )
2) Call SearchWord() for every cell (i, j) which has one of the
   first characters of dictionary words. In above example,
   we have "G" and "Q" as first characters.

SearchWord(Trie *root, i, j, visited[][N])
if root->leaf == true 
   print word 

if we have seen this element first time then make it visited.
   visited[i][j] = true
   do
      traverse all child of current root 
      k goes (0 to 26 ) [there are only 26 Alphabet] 
      add current char and search for next character 

      find next character which is adjacent to boggle[i][j]
      they are 8 adjacent cells of boggle[i][j] (i+1, j+1), 
      (i+1, j) (i-1, j) and so on.
   
   make it unvisited visited[i][j] = false

Ниже приведена реализация вышеуказанной идеи:

Выход:

GEE, GEEKS, QUIZ

Анализ сложности:

Временная сложность: O(4^(N^2)).
Даже после применения попытки временная сложность остается прежней. Для каждой ячейки есть 4 направления и есть N^2 ячеек. Таким образом, временная сложность составляет O (4 ^ (N ^ 2)).
Вспомогательное пространство: O(N^2).
Максимальная длина рекурсии может быть N^2, где N — сторона матрицы. Таким образом, сложность пространства составляет O (N ^ 2).

Эта статья предоставлена Нишант Сингх. Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью с помощью write.geeksforgeeks.org или отправить ее по адресу review-team@geeksforgeeks.org. Посмотрите, как ваша статья появится на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.

Microsoft

Boggle с помощью Trie

РЕКОМЕНДУЕМЫЕ СТАТЬИ