Рубрики

Вывести все пары анаграмм в заданном массиве строк

Строки

По заданному массиву строк найдите все пары анаграмм в данном массиве.
Пример:

Input: arr[] =  {"geeksquiz", "geeksforgeeks", "abcd",
                 "forgeeksgeeks", "zuiqkeegs"};
Output: (geeksforgeeks, forgeeksgeeks), (geeksquiz, zuiqkeegs)

Мы можем найти две строки , являются ли анаграмма или не в линейное время с помощью счетчика массива (см метода 2 из этого ).

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

C ++

#include <bits/stdc++.h>

using namespace std;

#define NO_OF_CHARS 256

  
/ * функция для проверки, являются ли две строки анаграммами друг друга * /

bool areAnagram(string str1, string str2)

{

    // Создаем два массива счетчиков и инициализируем все значения как 0

    int count[NO_OF_CHARS] = {0};

    int i;

  

    // Для каждого символа во входных строках счетчик приращений в

    // соответствующий массив

    for (i = 0; str1[i] && str2[i];  i++)

    {

        count[str1[i]]++;

        count[str2[i]]--;

    }

  

    // Если обе строки имеют разную длину. Удаление этого условия

    // вызовет сбой программы для таких строк, как "aaca" и "aca"

    if (str1[i] || str2[i])

      return false;

  

    // Посмотрим, есть ли ненулевое значение в массиве count

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

        if (count[i])

            return false;

     return true;

}

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

void findAllAnagrams(string arr[], int n)

{

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

        for (int j = i+1; j < n; j++)

            if (areAnagram(arr[i], arr[j]))

                cout << arr[i] << " is anagram of " << arr[j] << endl;

}

  

  
/ * Программа драйвера для проверки на печать printDups * /

int main()

{

    string arr[] = {"geeksquiz", "geeksforgeeks", "abcd", 

                    "forgeeksgeeks", "zuiqkeegs"};

    int n = sizeof(arr)/sizeof(arr[0]);

    findAllAnagrams(arr, n);

    return 0;

}

Джава

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

public class GFG 

{

    static final int NO_OF_CHARS = 256;

      

    / * функция, чтобы проверить, два ли

    строки - анаграммы друг друга * /

    static boolean areAnagram(String str1, String str2)

    {

        // Создаем два массива и инициализируем

        // все значения как 0

        int[] count = new int[NO_OF_CHARS];

        int i;

  

        // Для каждого символа во входных строках,

        // увеличиваем счетчик в соответствующем

        // подсчитать массив

        for (i = 0; i < str1.length() && i < str2.length();

                                                   i++)

        {

            count[str1.charAt(i)]++;

            count[str2.charAt(i)]--;

        }

  

        // Если обе строки имеют разную длину.

        // Удаление этого условия сделает программу

        // сбой для строк типа "aaca" и "aca"

        if (str1.length() != str2.length())

          return false;

  

        // Посмотрим, есть ли ненулевое значение в

        // подсчитать массив

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

            if (count[i] != 0)

                return false;

         return true;

    }

  

    // Эта функция печатает все пары анаграмм в

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

    static void findAllAnagrams(String arr[], int n)

    {

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

            for (int j = i+1; j < n; j++)

                if (areAnagram(arr[i], arr[j]))

                    System.out.println(arr[i] + 

                       " is anagram of " + arr[j]);

    }

  

    / * Программа драйвера для проверки на печать printDups * /

    public static void main(String args[])

    {

        String arr[] = {"geeksquiz", "geeksforgeeks",

                        "abcd", "forgeeksgeeks", 

                        "zuiqkeegs"};

        int n = arr.length;

        findAllAnagrams(arr, n);

    }

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

C #

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

using System;

  

class GFG 

{

    static int NO_OF_CHARS = 256;

      

    / * функция, чтобы проверить, два ли

    строки - анаграммы друг друга * /

    static bool areAnagram(String str1, String str2)

    {

        // Создаем два массива и инициализируем

        // все значения как 0

        int[] count = new int[NO_OF_CHARS];

        int i;

  

        // Для каждого символа во входных строках,

        // увеличиваем счетчик в соответствующем

        // подсчитать массив

        for (i = 0; i < str1.Length && 

                    i < str2.Length; i++)

        {

            count[str1[i]]++;

            count[str2[i]]--;

        }

  

        // Если обе строки имеют разную длину.

        // Удаление этого условия сделает программу

        // сбой для строк типа "aaca" и "aca"

        if (str1.Length != str2.Length)

        return false;

  

        // Посмотрим, есть ли ненулевое значение в

        // подсчитать массив

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

            if (count[i] != 0)

                return false;

        return true;

    }

  

    // Эта функция печатает все пары анаграмм в

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

    static void findAllAnagrams(String []arr, int n)

    {

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

            for (int j = i+1; j < n; j++)

                if (areAnagram(arr[i], arr[j]))

                    Console.WriteLine(arr[i] + 

                    " is anagram of " + arr[j]);

    }

  

    / * Программа драйвера для проверки на печать printDups * /

    public static void Main()

    {

        String []arr = {"geeksquiz", "geeksforgeeks",

                        "abcd", "forgeeksgeeks", 

                        "zuiqkeegs"};

        int n = arr.Length;

        findAllAnagrams(arr, n);

    }

}

  
// Этот код предоставлен нитин митталь


Выход:

geeksquiz is anagram of zuiqkeegs
geeksforgeeks is anagram of forgeeksgeeks

Временная сложность вышеуказанного решения составляет O (n 2 * m), где n — количество строк, а m — максимальная длина строки.

Оптимизации:
Мы можем оптимизировать вышеуказанное решение, используя следующие подходы.
1) Использование сортировки: мы можем отсортировать массив строк так, чтобы все анаграммы собрались вместе. Затем распечатайте все анаграммы путем линейного обхода отсортированного массива. Временная сложность этого решения составляет O (mnLogn) (мы будем делать O (nLogn) сравнений в сортировке, а сравнение займет O (m) времени)

2) Использование хеширования: мы можем построить хеш-функцию, например, XOR или сумму значений ASCII всех символов для строки. Используя такую хеш-функцию, мы можем построить хеш-таблицу. При создании хеш-таблицы мы можем проверить, хэшировано ли уже значение. Если да, мы можем вызвать areAnagrams (), чтобы проверить, действительно ли две строки являются анаграммами (обратите внимание, что xor или сумма значений ASCII недостаточны, см. Комментарий Каушика Леле здесь )

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

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

Вывести все пары анаграмм в заданном массиве строк

0.00 (0%) 0 votes