Рубрики

Учитывая последовательность слов, выведите все анаграммы вместе | Комплект 1

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

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

Ниже приведен еще один способ распечатать все анаграммы вместе. Возьмите два вспомогательных массива, массив индекса и массив слов. Заполните массив слов заданной последовательностью слов. Сортировать каждое отдельное слово из массива слов. Наконец, сортируйте массив слов и отслеживайте соответствующие индексы. После сортировки все анаграммы объединяются. Используйте индексный массив для печати строк из исходного массива строк.

Давайте разберемся с шагами со следующей входной последовательностью слов:

"cat", "dog", "tac", "god", "act"

1) Создайте два вспомогательных массива index [] и words []. Скопируйте все заданные слова в слова [] и сохраните исходные индексы в index []

index[]:  0   1   2   3   4
words[]: cat dog tac god act

2) Сортировать отдельные слова в словах []. Индексный массив не изменяется.

index[]:   0    1    2    3    4
words[]:  act  dgo  act  dgo  act

3) Сортировать массив слов. Сравните отдельные слова, используя strcmp () для сортировки

index:     0    2    4    1    3
words[]:  act  act  act  dgo  dgo

4) Все анаграммы собираются вместе. Но слова изменяются в массиве слов. Чтобы напечатать исходные слова, возьмите index из массива index и используйте его в исходном массиве. Мы получаем

"cat tac act dog god"

Ниже приведены реализации вышеуказанного алгоритма. В следующей программе массив структуры «Word» используется для хранения индексного и словесного массивов. DupArray — еще одна структура, в которой хранится массив структур «Word».

C ++

// Программа на C ++ для печати всех анаграмм вместе
#include <bits/stdc++.h>
#include<string.h>

using namespace std;

  
// структура для каждого слова дублирующего массива

class Word 

    public:

    char* str; // хранить само слово

    int index; // индекс слова в исходном массиве

}; 

  
// структура для представления дублирующего массива.

class DupArray 

{

    public:

    Word* array; // Массив слов

    int size; // Размер массива

}; 

  
// Создаем объект DupArray, который содержит массив слов

DupArray* createDupArray(char* str[], int size) 

    // Выделим память для dupArray и всех его членов

    DupArray* dupArray = new DupArray();

    dupArray->size = size; 

    dupArray->array = new Word[(dupArray->size * sizeof(Word))]; 

  

    // Копируем одно за другим слова из данного wordArray в dupArray

    int i; 

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

    

        dupArray->array[i].index = i; 

        dupArray->array[i].str = new char[(strlen(str[i]) + 1)]; 

        strcpy(dupArray->array[i].str, str[i]); 

    

  

    return dupArray; 

  
// Сравнить два символа. Используется в qsort () для
// сортировка массива символов (Word)

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

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

  
// Сравнить два слова. Используется в qsort ()
// для сортировки массива слов

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

    Word* a1 = (Word*)a; 

    Word* b1 = (Word*)b; 

    return strcmp(a1->str, b1->str); 

  
// Дан список слов в wordArr [],

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

    // Шаг 1: Создать копию всех слов, присутствующих в данном wordArr.

    // Копия также будет иметь оригинальные индексы слов

    DupArray* dupArray = createDupArray(wordArr, size); 

  

    // Шаг 2: перебрать все слова в dupArray и отсортировать

    // отдельные слова.

    int i; 

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

        qsort(dupArray->array[i].str, 

            strlen(dupArray->array[i].str), sizeof(char), compChar); 

  

    // Шаг 3: теперь сортируем массив слов в dupArray

    qsort(dupArray->array, size, sizeof(dupArray->array[0]), compStr); 

  

    // Шаг 4: Теперь все слова в dupArray вместе, но они

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

    // получить соответствующее оригинальное слово

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

        cout<<wordArr[dupArray->array[i].index]<<" "

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

int main() 

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

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

    printAnagramsTogether(wordArr, size); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

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

  
// структура для каждого слова дублирующего массива

struct Word {

    char* str; // хранить само слово

    int index; // индекс слова в исходном массиве

};

  
// структура для представления дублирующего массива.

struct DupArray {

    struct Word* array; // Массив слов

    int size; // Размер массива

};

  
// Создаем объект DupArray, который содержит массив слов

struct DupArray* createDupArray(char* str[], int size)

{

    // Выделим память для dupArray и всех его членов

    struct DupArray* dupArray = (struct DupArray*)malloc(sizeof(struct DupArray));

    dupArray->size = size;

    dupArray->array = (struct Word*)malloc(dupArray->size * sizeof(struct Word));

  

    // Копируем одно за другим слова из данного wordArray в dupArray

    int i;

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

        dupArray->array[i].index = i;

        dupArray->array[i].str = (char*)malloc(strlen(str[i]) + 1);

        strcpy(dupArray->array[i].str, str[i]);

    }

  

    return dupArray;

}

  
// Сравнить два символа. Используется в qsort () для сортировки массива
// символы (Word)

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

{

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

}

  
// Сравнить два слова. Используется в qsort () для сортировки массива слов

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

{

    struct Word* a1 = (struct Word*)a;

    struct Word* b1 = (struct Word*)b;

    return strcmp(a1->str, b1->str);

}

  
// Дан список слов в wordArr [],

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

{

    // Шаг 1: Создать копию всех слов, присутствующих в данном wordArr.

    // Копия также будет иметь оригинальные индексы слов

    struct DupArray* dupArray = createDupArray(wordArr, size);

  

    // Шаг 2: перебрать все слова в dupArray и отсортировать

    // отдельные слова.

    int i;

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

        qsort(dupArray->array[i].str,

              strlen(dupArray->array[i].str), sizeof(char), compChar);

  

    // Шаг 3: теперь сортируем массив слов в dupArray

    qsort(dupArray->array, size, sizeof(dupArray->array[0]), compStr);

  

    // Шаг 4: Теперь все слова в dupArray вместе, но они

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

    // получить соответствующее оригинальное слово

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

        printf("%s ", wordArr[dupArray->array[i].index]);

}

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

int main()

{

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

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

    printAnagramsTogether(wordArr, size);

    return 0;

}

Джава

// Java-программа для печати всех анаграмм вместе

import java.util.Arrays;

import java.util.Comparator;

public class GFG {

    // класс для каждого слова дублирующего массива

    static class Word {

        String str; // хранить само слово

        int index; // индекс слова в

        // исходный массив

  

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

        Word(String str, int index)

        {

            this.str = str;

            this.index = index;

        }

    }

  

    // класс для представления дублирующего массива.

    static class DupArray {

        Word[] array; // Массив слов

        int size; // Размер массива

  

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

        public DupArray(String str[], int size)

        {

            this.size = size;

            array = new Word[size];

  

            // Один за другим копируем слова из

            // присваиваем wordArray для dupArray

            int i;

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

                // создаем слово Object с

                // str [i] как str и индекс как i

                array[i] = new Word(str[i], i);

            }

        }

    }

  

    // Сравнить два слова. Используется в Arrays.sort () для

    // сортировка массива слов

    static class compStr implements Comparator<Word> {

        public int compare(Word a, Word b)

        {

            return a.str.compareTo(b.str);

        }

    }

  

    // Дан список слов в wordArr [],

    static void printAnagramsTogether(String wordArr[],

                                      int size)

    {

        // Шаг 1: Создать копию всех присутствующих слов

        // в данном слове Arr. Копия также будет иметь

        // оригинальные индексы слов

        DupArray dupArray = new DupArray(wordArr, size);

  

        // Шаг 2: перебрать все слова в

        // dupArray и сортировка отдельных слов.

        int i;

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

            char[] char_arr = dupArray.array[i].str.toCharArray();

            Arrays.sort(char_arr);

            dupArray.array[i].str = new String(char_arr);

        }

  

        // Шаг 3: теперь сортируем массив слов в

        // dupArray

        Arrays.sort(dupArray.array, new compStr());

  

        // Шаг 4: Теперь все слова в dupArray вместе,

        // но эти слова изменены. Используйте индекс

        // член слова struct для получения соответствующего

        // оригинальное слово

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

            System.out.print(wordArr[dupArray.array[i].index] + " ");

    }

  

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

    public static void main(String args[])

    {

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

        int size = wordArr.length;

        printAnagramsTogether(wordArr, size);

    }

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

питон

# Программа Python для печати всех анаграмм вместе

  
# структура для каждого слова дублирующего массива

class Word(object):

    def __init__(self, string, index):

        self.string = string

        self.index = index

  
# Создайте объект DupArray, который содержит массив
Количество слов

def createDupArray(string, size):

    dupArray = []

  

    # Один за другим копировать слова из данного wordArray

    # to dupArray

    for i in xrange(size):

        dupArray.append(Word(string[i], i))

  

    return dupArray

  
# Приведен список слов в wordArr []

def printAnagramsTogether(wordArr, size):

    # Шаг 1. Создайте копию всех слов, присутствующих в

    # данный wordArr.

    # Копия также будет иметь оригинальные указатели слов

    dupArray = createDupArray(wordArr, size)

  

    # Шаг 2: перебрать все слова в dupArray и отсортировать

    # отдельные слова.

    for i in xrange(size):

        dupArray[i].string = ''.join(sorted(dupArray[i].string))

  

    # Шаг 3: Теперь сортируем массив слов в dupArray

    dupArray = sorted(dupArray, key = lambda k: k.string)

  

    # Шаг 4: Теперь все слова в dupArray вместе, но

    # эти слова изменены. Используйте индексный член слова

    # struct для получения соответствующего исходного слова

    for word in dupArray:

        print wordArr[word.index],

  
# Драйверная программа

wordArr = ["cat", "dog", "tac", "god", "act"]

size = len(wordArr)

printAnagramsTogether(wordArr, size)

  
# Этот код предоставлен BHAVYA JAIN


Выход:

cat tac act dog god 

Сложность времени: пусть будет N слов, и каждое слово имеет максимум M символов. Верхняя граница O (NMLogM + MNLogN).
Шаг 2 занимает O (NMLogM) время. Сортировка слова занимает максимальное время O (MLogM). Таким образом, сортировка N слов занимает O (NMLogM) времени. шаг 3 — O (MNLogN). Сортировка массива слов — сравнение NLogN. Сравнение может занять максимальное время O (M). Так что время сортировки массива слов будет O (MNLogN).

Использование hashmap

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

Джава

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

import java.util.*; 

  

public class FindAnagrams { 

  

    private static void printAnagrams(String arr[]) 

    

        HashMap<String, List<String> > map = new HashMap<>(); 

  

        // цикл по всем словам

        for (int i = 0; i < arr.length; i++) { 

  

            // преобразовать в массив символов, отсортировать и

            // затем преобразовать в строку

            String word = arr[i]; 

            char[] letters = word.toCharArray(); 

            Arrays.sort(letters); 

            String newWord = new String(letters); 

  

            // вычисляем хеш-код строки

            // после сортировки

            if (map.containsKey(newWord)) { 

  

                map.get(newWord).add(word); 

            

            else

  

                // мы в первый раз

                // добавление слова для определенного

                // хэш-код

                List<String> words = new ArrayList<>(); 

                words.add(word); 

                map.put(newWord, words); 

            

        

  

        // выводим все значения, где размер> 1

        // Если вы хотите распечатать неанаграммы,

        // просто выводим значения, имеющие размер = 1

        for (String s : map.keySet()) { 

            List<String> values = map.get(s); 

            if (values.size() > 1) { 

                System.out.print(values); 

            

        

    

  

    public static void main(String[] args) 

    

  

        // Драйвер программы

        String arr[] = { "cat", "dog", "tac", "god", "act" }; 

        printAnagrams(arr); 

    

python3

from collections import defaultdict 

  

def printAnagramsTogether(words):

    groupedWords = defaultdict(list)

  

    # Соберите все слова анаграммы вместе в словаре

    # где ключ сортируется слово

    for word in words:

        groupedWords["".join(sorted(word))].append(word)

  

    # Распечатать все анаграммы вместе

    for group in groupedWords.values():

        print(" ".join(group))      

  

  

if __name__ == "__main__":   

    arr =  ["cat", "dog", "tac", "god", "act"]  

    printAnagramsTogether(arr)     

C #

// C # программа для печати анаграмм
// вместе используем словарь

using System;

using System.Collections.Generic;

  

class GFG

    private static void printAnagrams(String []arr) 

    

        Dictionary<String, 

              List<String> > map = new Dictionary<String, 

                                             List<String> >(); 

  

        // цикл по всем словам

        for (int i = 0; i < arr.Length; i++) 

        

  

            // преобразовать в массив символов, отсортировать и

            // затем преобразовать в строку

            String word = arr[i]; 

            char[] letters = word.ToCharArray(); 

            Array.Sort(letters); 

            String newWord = new String(letters); 

  

            // вычисляем хеш-код строки

            // после сортировки

            if (map.ContainsKey(newWord)) 

            

                map[newWord].Add(word); 

            

            else 

            

  

                // мы в первый раз

                // добавление слова для определенного

                // хэш-код

                List<String> words = new List<String>(); 

                words.Add(word); 

                map.Add(newWord, words); 

            

        

  

        // выводим все значения, где размер> 1

        // Если вы хотите распечатать неанаграммы,

        // просто выводим значения, имеющие размер = 1

        List<String> value = new List<String>();

        foreach(KeyValuePair<String, 

                        List<String>> entry in map)

        {

            value.Add(entry.Key);

        }

        int k = 0;

        foreach(KeyValuePair<String,

                        List<String>> entry in map)

        

            List<String> values = map[value[k++]]; 

            if (values.Count > 1) 

            

                Console.Write("["); 

                int len = 1;

                foreach(String s in values)

                {

                    Console.Write(s);

                    if(len++<values.Count)

                        Console.Write(", "); 

                }

                Console.Write("]"); 

            

        

    

  

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

    public static void Main(String[] args) 

    

        String []arr = { "cat", "dog", "tac",

                                "god", "act" }; 

        printAnagrams(arr); 

    

  
// Этот код предоставлен Принчи Сингхом

Выход :

[cat, tac, act][dog, god]

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

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

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

Учитывая последовательность слов, выведите все анаграммы вместе | Комплект 1

0.00 (0%) 0 votes