Рубрики

Учитывая последовательность слов, выведите все анаграммы вместе | Набор 2

Учитывая массив слов, выведите все анаграммы вместе. Например, если заданным массивом является {«cat», «dog», «tac», «god», «act»}, то результатом может быть «cat tac act dog god».

Мы обсудили два разных метода в предыдущем посте . В этом посте обсуждается более эффективное решение.

Структура данных Trie может быть использована для более эффективного решения. Вставьте отсортированный порядок каждого слова в дереве. Поскольку все анаграммы будут заканчиваться на одном и том же листовом узле. Мы можем начать связанный список в конечных узлах, где каждый узел представляет индекс исходного массива слов. Наконец, пройдите через Три. Пересекая Trie, перебирайте каждый связанный список по одной строке за раз. Ниже приведены подробные шаги.

1) Создать пустую Trie
2) Один за другим взять все слова входной последовательности. Следуйте за каждым словом
… А ) Скопируйте слово в буфер.
Б) Сортировка буфера
… В ) Вставьте отсортированный буфер и индекс этого слова в Trie. Каждый листовой узел Trie является главой списка Index. В списке указателей хранится указатель слов в оригинальной последовательности. Если отсортированный буфер уже присутствует, мы вставляем индекс этого слова в список индексов.
3) Траверс Три. При обходе, если вы достигнете конечного узла, просмотрите список индексов. И распечатать все слова, используя индекс, полученный из списка индексов.

C ++

// Эффективная программа для печати всех анаграмм вместе
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

  
#define NO_OF_CHARS 26

  
// Структура для представления списка узлов для индексов слов в
// данная последовательность. Узлы списка используются для подключения
// анаграммы на листовых узлах Три

struct IndexNode

{

    int index;

    struct IndexNode* next;

};

  
// Структура для представления узла Trie

struct TrieNode

{

    bool isEnd;  // указывает конец слова

    struct TrieNode* child[NO_OF_CHARS]; // 26 слотов для каждого от 'a' до 'z'

    struct IndexNode* head; // заголовок списка индексов

};

  

  
// Служебная функция для создания нового узла Trie

struct TrieNode* newTrieNode()

{

    struct TrieNode* temp = new TrieNode;

    temp->isEnd = 0;

    temp->head = NULL;

    for (int i = 0; i < NO_OF_CHARS; ++i)

        temp->child[i] = NULL;

    return temp;

}

  
/ * Следующая функция необходима для библиотечной функции qsort (). обращаться

   http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ * /

int compare(const void* a, const void* b)

return *(char*)a - *(char*)b; }

  
/ * Утилита для создания нового узла связанного списка * /

struct IndexNode* newIndexNode(int index)

{

    struct IndexNode* temp = new IndexNode;

    temp->index = index;

    temp->next = NULL;

    return temp;

}

  
// Утилита для вставки слова в Trie

void insert(struct TrieNode** root, char* word, int index)

{

    // Базовый вариант

    if (*root == NULL)

        *root = newTrieNode();

  

    if (*word != '\0')

        insert( &( (*root)->child[tolower(*word) - 'a'] ), word+1, index );

    else  // Если достигнут конец слова

    {

        // Вставляем индекс этого слова в конец индекса связанного списка

        if ((*root)->isEnd)

        {

            IndexNode* pCrawl = (*root)->head;

            while( pCrawl->next )

                pCrawl = pCrawl->next;

            pCrawl->next = newIndexNode(index);

        }

        else  // Если индексный список пуст

        {

            (*root)->isEnd = 1;

            (*root)->head = newIndexNode(index);

        }

    }

}

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

void printAnagramsUtil(struct TrieNode* root, char *wordArr[])

{

    if (root == NULL)

        return;

  

    // Если достигнут ведущий узел, распечатать все анаграммы, используя индексы

    // хранится в индексном списке

    if (root->isEnd)

    {

        // пройти список

        IndexNode* pCrawl = root->head;

        while (pCrawl != NULL)

        {

            printf( "%s ", wordArr[ pCrawl->index ] );

            pCrawl = pCrawl->next;

        }

    }

  

    for (int i = 0; i < NO_OF_CHARS; ++i)

        printAnagramsUtil(root->child[i], wordArr);

}

  
// Основная функция, которая печатает все анаграммы вместе. WordArr [] является входным
// последовательность слов.

void printAnagramsTogether(char* wordArr[], int size)

{

    // Создать пустую Trie

    struct TrieNode* root = NULL;

  

    // перебирать все входные слова

    for (int i = 0; i < size; ++i)

    {

        // Создать буфер для этого слова и скопировать слово в буфер

        int len = strlen(wordArr[i]);

        char *buffer = new char[len+1];

        strcpy(buffer, wordArr[i]);

  

        // Сортировка буфера

        qsort( (void*)buffer, strlen(buffer), sizeof(char), compare );

  

        // Вставляем отсортированный буфер и его исходный индекс в Trie

        insert(&root,  buffer, i);

    }

  

    // Пройдемся по построенному Trie и напечатаем все анаграммы вместе

    printAnagramsUtil(root, wordArr);

}

  

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    char* wordArr[] = {"cat", "dog", "tac", "god", "act", "gdo"};

    int size = sizeof(wordArr) / sizeof(wordArr[0]);

    printAnagramsTogether(wordArr, size);

    return 0;

}

Джава

// Эффективная программа для печати всех
// анаграммы вместе

import java.util.Arrays;

import java.util.LinkedList;

  

public class GFG 

    static final int NO_OF_CHARS = 26;

      

    // Класс для представления узла Trie

    static class TrieNode

    {

        boolean isEnd;  // указывает конец слова

          

        // 26 слотов для каждого от 'a' до 'z'

        TrieNode[] child = new TrieNode[NO_OF_CHARS];

          

        // заголовок списка индексов

        LinkedList<Integer> head; 

          

        // конструктор

        public TrieNode() 

        {

            isEnd = false;

            head = new LinkedList<>();

            for (int i = 0; i < NO_OF_CHARS; ++i)

                child[i] = null;

        }

    }

       

    // Утилита для вставки слова в Trie

    static TrieNode insert(TrieNode root,String word,

                                int index, int i)

    {

        // Базовый вариант

        if (root == null)

        {

            root = new TrieNode();

        }

          

        if (i < word.length() )

        {

            int index1 = word.charAt(i) - 'a';

            root.child[index1] = insert(root.child[index1],

                                       word, index, i+1 );

        }

        else  // Если достигнут конец слова

        {

            // Вставляем индекс этого слова в конец

            // индексировать связанный список

            if (root.isEnd == true)

            {

                root.head.add(index);

            }

            else // Если индексный список пуст

            {

                root.isEnd = true;

                root.head.add(index);

            }

        }

        return root;

    }

  

    // Эта функция пересекает построенный файл. Когда лист

    // узел достигнут, все слова соединены на этом листе

    // узел - это анаграммы. Таким образом, он пересекает список на листе

    // узел и использует сохраненный индекс для печати оригинальных слов

    static void printAnagramsUtil(TrieNode root, 

                                      String wordArr[])

    {

        if (root == null)

            return;

       

        // Если достигнут ведущий узел, распечатать все анаграммы

        // используя индексы, хранящиеся в связанном списке индексов

        if (root.isEnd)

        {

            // пройти список

            for(Integer pCrawl: root.head)

                System.out.println(wordArr[pCrawl]);

        }

       

        for (int i = 0; i < NO_OF_CHARS; ++i)

            printAnagramsUtil(root.child[i], wordArr);

    }

       

    // Основная функция, которая печатает все анаграммы вместе.

    // wordArr [] - входная последовательность слов.

    static void printAnagramsTogether(String wordArr[], 

                                               int size)

    {

        // Создать пустую Trie

        TrieNode root = null;

       

        // перебирать все входные слова

        for (int i = 0; i < size; ++i)

        {

            // Создать буфер для этого слова и скопировать

            // слово в буфер

            char[] buffer = wordArr[i].toCharArray();

             

            // Сортировка буфера

            Arrays.sort(buffer);

       

            // Вставляем отсортированный буфер и его оригинал

            // указатель на три

            root = insert(root, new String(buffer), i, 0);

              

        }

          

        // Пройдемся по построенному Trie и напечатаем все анагрмы

        // вместе

        printAnagramsUtil(root, wordArr);

    }

       

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[])

    {

        String wordArr[] = {"cat", "dog", "tac", "god",

                                        "act", "gdo"};

        int size = wordArr.length;

        printAnagramsTogether(wordArr, size);

    }

}
// Этот код предоставлен Sumit Ghosh

C #

// Эффективная программа на C # для печати всех
// анаграммы вместе

using System;

using System.Collections.Generic; 

  

class GFG 

    static readonly int NO_OF_CHARS = 26; 

      

    // Класс для представления узла Trie

    public class TrieNode 

    

        // указывает конец слова

        public bool isEnd; 

          

        // 26 слотов для каждого от 'a' до 'z'

        public TrieNode[] child = new TrieNode[NO_OF_CHARS]; 

          

        // заголовок списка индексов

        public List<int> head; 

          

        // конструктор

        public TrieNode() 

        

            isEnd = false

            head = new List<int>(); 

            for (int i = 0; i < NO_OF_CHARS; ++i) 

                child[i] = null

        

    

      

    // Утилита для вставки слова в Trie

    static TrieNode insert(TrieNode root,String word, 

                                int index, int i) 

    

        // Базовый вариант

        if (root == null

        

            root = new TrieNode(); 

        

          

        if (i < word.Length ) 

        

            int index1 = word[i] - 'a'

            root.child[index1] = insert(root.child[index1], 

                                    word, index, i + 1 ); 

        

          

        // Если достигнут конец слова

        else 

        

            // Вставляем индекс этого слова в конец

            // индексировать связанный список

            if (root.isEnd == true

            

                root.head.Add(index); 

            

              

            // Если индексный список пуст

            else 

            

                root.isEnd = true

                root.head.Add(index); 

            

        

        return root; 

    

  

    // Эта функция пересекает построенный файл.

    // Когда достигнут листовой узел, все слова

    // на этом листовом узле связаны анаграммы.

    // Таким образом, он пересекает список на листовом узле

    // и использует сохраненный индекс для печати оригинальных слов

    static void printAnagramsUtil(TrieNode root, 

                                    String []wordArr) 

    

        if (root == null

            return

      

        // Если достигнут ведущий узел,

        // распечатать все анаграммы, используя

        // индексы, хранящиеся в списке связанных индексов

        if (root.isEnd) 

        

            // пройти список

            foreach(int pCrawl in root.head) 

                Console.WriteLine(wordArr[pCrawl]); 

        

      

        for (int i = 0; i < NO_OF_CHARS; ++i) 

            printAnagramsUtil(root.child[i], wordArr); 

    

      

    // Основная функция, которая печатает

    // все анаграммы вместе. wordArr []

    // входная последовательность слов.

    static void printAnagramsTogether(String []wordArr, 

                                            int size) 

    

        // Создать пустую Trie

        TrieNode root = null

      

        // перебирать все входные слова

        for (int i = 0; i < size; ++i) 

        

            // Создать буфер для этого слова

            // и скопировать слово в буфер

            char[] buffer = wordArr[i].ToCharArray(); 

              

            // Сортировка буфера

            Array.Sort(buffer); 

      

            // Вставляем отсортированный буфер и

            // его первоначальный индекс в три

            root = insert(root, new String(buffer), i, 0); 

              

        

          

        // Пройдемся по построенному Три и

        // выводим все анаграммы вместе

        printAnagramsUtil(root, wordArr); 

    

      

    // Код драйвера

    public static void Main(String []args) 

    

        String []wordArr = {"cat", "dog", "tac", "god"

                                        "act", "gdo"}; 

        int size = wordArr.Length; 

        printAnagramsTogether(wordArr, size); 

    

  
// Этот код предоставлен 29AjayKumar


Выход:

cat
tac
act
dog
god
gdo

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Учитывая последовательность слов, выведите все анаграммы вместе | Набор 2

0.00 (0%) 0 votes