Рубрики

Проверьте, являются ли две строки анаграммой друг друга

Напишите функцию, чтобы проверить, являются ли две данные строки анаграммой друг друга или нет. Анаграмма строки — это другая строка, содержащая те же символы, только порядок символов может быть другим. Например, «abcd» и «dabc» являются анаграммами друг друга.

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Способ 1 (использовать сортировку)

  1. Сортировать обе строки
  2. Сравните отсортированные строки

C ++

// C ++ программа для проверки, являются ли две строки анаграммами
// друг друга
#include <bits/stdc++.h>

using namespace std;

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

bool areAnagram(string str1, string str2)

{

    // Получить длины обеих строк

    int n1 = str1.length();

    int n2 = str2.length();

  

    // Если длина обеих строк не одинакова, то они

    // не может быть анаграммой

    if (n1 != n2)

        return false;

  

    // Сортировка обеих строк

    sort(str1.begin(), str1.end());

    sort(str2.begin(), str2.end());

  

    // Сравнить отсортированные строки

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

        if (str1[i] != str2[i])

            return false;

  

    return true;

}

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

int main()

{

    string str1 = "test";

    string str2 = "ttew";

    if (areAnagram(str1, str2))

        cout << "The two strings are anagram of each other";

    else

        cout << "The two strings are not anagram of each other";

  

    return 0;

}

Джава

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

import java.io.*;

import java.util.Arrays;

import java.util.Collections;

  

class GFG {

  

    / * функция для проверки наличия двух строк

    анаграмма друг друга * /

    static boolean areAnagram(char[] str1, char[] str2)

    {

        // Получить длины обеих строк

        int n1 = str1.length;

        int n2 = str2.length;

  

        // Если длина обеих строк не одинакова,

        // тогда они не могут быть анаграммами

        if (n1 != n2)

            return false;

  

        // Сортировка обеих строк

        Arrays.sort(str1);

        Arrays.sort(str2);

  

        // Сравнить отсортированные строки

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

            if (str1[i] != str2[i])

                return false;

  

        return true;

    }

  

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

    public static void main(String args[])

    {

        char str1[] = { 't', 'e', 's', 't' };

        char str2[] = { 't', 't', 'e', 'w' };

        if (areAnagram(str1, str2))

            System.out.println("The two strings are"

                               + " anagram of each other");

        else

            System.out.println("The two strings are not"

                               + " anagram of each other");

    }

}

  
// Этот код предоставлен Никитой Тивари.

питон

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

  
# функция, чтобы проверить, являются ли две строки анаграммой
# друг друга

def areAnagram(str1, str2): 

    # Получить длины обеих строк

    n1 = len(str1) 

    n2 = len(str2) 

  

    # Если длина обеих строк не одинакова, то

    # они не могут быть анаграммами

    if n1 != n2: 

        return 0

  

    # Сортировать обе строки

    str1 = sorted(str1)

    str2 = sorted(str2)

  

    # Сравнить отсортированные строки

    for i in range(0, n1): 

        if str1[i] != str2[i]: 

            return 0

  

    return 1

  

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

str1 = "test"

str2 = "ttew"

if areAnagram(str1, str2): 

    print ("The two strings are anagram of each other")

else

    print ("The two strings are not anagram of each other")

  
# Этот код предоставлен Bhavya Jain

C #

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

using System;

using System.Collections;

class GFG {

  

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

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

    public static bool areAnagram(ArrayList str1,

                                  ArrayList str2)

    {

        // Получить длины обеих строк

        int n1 = str1.Count;

        int n2 = str2.Count;

  

        // Если длина обеих строк не

        // то же самое, тогда они не могут быть анаграммами

        if (n1 != n2) {

            return false;

        }

  

        // Сортировка обеих строк

        str1.Sort();

        str2.Sort();

  

        // Сравнить отсортированные строки

        for (int i = 0; i < n1; i++) {

            if (str1[i] != str2[i]) {

                return false;

            }

        }

  

        return true;

    }

  

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

    public static void Main(string[] args)

    {

        // создаем и инициализируем новый ArrayList

        ArrayList str1 = new ArrayList();

        str1.Add('t');

        str1.Add('e');https://www.youtube.com/watch?v=Tztc73r8348

        str1.Add('s');

        str1.Add('t');

        // создаем и инициализируем новый ArrayList

        ArrayList str2 = new ArrayList();

        str2.Add('t');

        str2.Add('t');

        str2.Add('e');

        str2.Add('w');

  

        if (areAnagram(str1, str2)) {

            Console.WriteLine("The two strings are"

                              + " anagram of each other");

        }

        else {

            Console.WriteLine("The two strings are not"

                              + " anagram of each other");

        }

    }

}

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

Выход:

The two strings are not anagram of each other

Сложность времени: O (nLogn)

Способ 2 (подсчет символов)
Этот метод предполагает, что набор возможных символов в обеих строках невелик. В следующей реализации предполагается, что символы хранятся с использованием 8 битов, и может быть 256 возможных символов.

  1. Создайте массивы счетчиков размером 256 для обеих строк. Инициализируйте все значения в массивах count как 0.
  2. Перебирайте каждый символ в обеих строках и увеличивайте количество символов в соответствующих массивах.
  3. Сравните количество массивов. Если оба массива одинаковы, вернуть true.

C ++

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

using namespace std;

#define NO_OF_CHARS 256

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

bool areAnagram(char* str1, char* str2)

{

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

    int count1[NO_OF_CHARS] = { 0 };

    int count2[NO_OF_CHARS] = { 0 };

    int i;

  

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

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

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

        count1[str1[i]]++;

        count2[str2[i]]++;

    }

  

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

    // условие приведет к сбою программы для таких строк, как

    // "ака" и "ака"

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

        return false;

  

    // Сравнить массивы

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

        if (count1[i] != count2[i])

            return false;

  

    return true;

}

  
/ * Код водителя * /

int main()

{

    char str1[] = "geeksforgeeks";

    char str2[] = "forgeeksgeeks";

    if (areAnagram(str1, str2))

        cout << "The two strings are anagram of each other";

    else

        cout << "The two strings are not anagram of each other";

  

    return 0;

}

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

С

// C программа для проверки наличия двух строк
// анаграммы друг друга
#include <stdio.h>
#define NO_OF_CHARS 256

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

   друг с другом */

bool areAnagram(char* str1, char* str2)

{

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

    int count1[NO_OF_CHARS] = { 0 };

    int count2[NO_OF_CHARS] = { 0 };

    int i;

  

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

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

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

        count1[str1[i]]++;

        count2[str2[i]]++;

    }

  

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

    // условие приведет к сбою программы для таких строк, как

    // "ака" и "ака"

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

        return false;

  

    // Сравнить массивы

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

        if (count1[i] != count2[i])

            return false;

  

    return true;

}

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

int main()

{

    char str1[] = "geeksforgeeks";

    char str2[] = "forgeeksgeeks";

    if (areAnagram(str1, str2))

        printf("The two strings are anagram of each other");

    else

        printf("The two strings are not anagram of each other");

  

    return 0;

}

Джава

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

import java.io.*;

import java.util.*;

  

class GFG {

  

    static int NO_OF_CHARS = 256;

  

    / * функция для проверки наличия двух строк

    являются анаграммами друг друга * /

    static boolean areAnagram(char str1[], char str2[])

    {

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

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

        int count1[] = new int[NO_OF_CHARS];

        Arrays.fill(count1, 0);

        int count2[] = new int[NO_OF_CHARS];

        Arrays.fill(count2, 0);

        int i;

  

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

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

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

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

             i++) {

            count1[str1[i]]++;

            count2[str2[i]]++;

        }

  

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

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

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

        if (str1.length != str2.length)

            return false;

  

        // Сравнить массивы

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

            if (count1[i] != count2[i])

                return false;

  

        return true;

    }

  

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

    public static void main(String args[])

    {

        char str1[] = ("geeksforgeeks").toCharArray();

        char str2[] = ("forgeeksgeeks").toCharArray();

  

        if (areAnagram(str1, str2))

            System.out.println("The two strings are"

                               + "anagram of each other");

        else

            System.out.println("The two strings are not"

                               + " anagram of each other");

    }

}

  
// Этот код предоставлен Никитой Тивари.

питон

# Программа Python для проверки, являются ли две строки анаграммами
# друг с другом

NO_OF_CHARS = 256

  
# Функция, чтобы проверить, являются ли две строки анаграммой
# друг с другом

def areAnagram(str1, str2):

  

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

    count1 = [0] * NO_OF_CHARS

    count2 = [0] * NO_OF_CHARS

  

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

    # в соответствующем массиве count

    for i in str1:

        count1[ord(i)]+= 1

  

    for i in str2:

        count2[ord(i)]+= 1

  

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

    # условие приведет к сбою программы для таких строк, как

    # "аака" и "ака"

    if len(str1) != len(str2):

        return 0

  

    # Сравнить массивы

    for i in xrange(NO_OF_CHARS):

        if count1[i] != count2[i]:

            return 0

  

    return 1

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

str1 = "geeksforgeeks"

str2 = "forgeeksgeeks"

if areAnagram(str1, str2):

    print "The two strings are anagram of each other"

else:

    print "The two strings are not anagram of each other"

  
# Этот код предоставлен Bhavya Jain

C #

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

  

using System;

  

public class GFG {

  

    static int NO_OF_CHARS = 256;

  

    / * функция для проверки наличия двух строк

    являются анаграммами друг друга * /

    static bool areAnagram(char[] str1, char[] str2)

    {

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

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

        int[] count1 = new int[NO_OF_CHARS];

        int[] count2 = new int[NO_OF_CHARS];

        int i;

  

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

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

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

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

             i++) {

            count1[str1[i]]++;

            count2[str2[i]]++;

        }

  

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

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

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

        if (str1.Length != str2.Length)

            return false;

  

        // Сравнить массивы

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

            if (count1[i] != count2[i])

                return false;

  

        return true;

    }

  

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

    public static void Main()

    {

        char[] str1 = ("geeksforgeeks").ToCharArray();

        char[] str2 = ("forgeeksgeeks").ToCharArray();

  

        if (areAnagram(str1, str2))

            Console.WriteLine("The two strings are"

                              + "anagram of each other");

        else

            Console.WriteLine("The two strings are not"

                              + " anagram of each other");

    }

}

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

Выход:

The two strings are anagram of each other

Метод 3 (подсчет символов с использованием одного массива)
Вышеуказанная реализация может дополнительно использовать только один массив счетчиков вместо двух. Мы можем увеличивать значение в массиве count для символов в str1 и уменьшать для символов в str2. Наконец, если все значения счетчика равны 0, тогда две строки являются анаграммами друг друга. Спасибо Ace за предложенную оптимизацию.

bool areAnagram(char* str1, char* str2)

{

    // Создаем массив count и инициализируем все значения как 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;

}

Сложность времени: O (n)

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

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

Проверьте, являются ли две строки анаграммой друг друга

0.00 (0%) 0 votes