Дійсні анаграми


Рівень складності Легко
Часто запитують у Амазонка Goldman Sachs Google Microsoft Нагарро
Анаграма Хешування

У задачі “Дійсні анаграми” ми подали дві струни str1 та str2. З’ясуйте, що обидва рядки є анаграмами чи ні. Якщо вони є анаграми return true ще повернути false.

Приклад

Вхідний сигнал:

str1 = “abcbac”

str2 = "aabbcc"

вихід:

правда

Пояснення:

Оскільки str2 може бути сформований шляхом перестановки всіх слів str1, то результат буде "правда ”.

Алгоритм

  1. Знайдіть довжину обох рядків
  2. сортувати обидва рядки за алфавітом
  3. Порівняйте обидва рядки
  4. Якщо рівний прибуток "Правда" ще повернути "помилковий"

Пояснення

Анаграми - це ті самі слова, які можна розташувати в порядку, в якому обидва рядки виглядають однаково, і створює одне і те саме слово після їх перестановки.

Приклад: тихий - це слово, яке можна розташувати в порядку і змусити слово слухати, тому обидва слова є анаграмами одне одного.

Наш код - визначити, чи є дані рядки дійсними анаграми чи ні, тому наша основна ідея полягає в тому, щоб спершу знайти довжину рядка, якщо виявиться, що довжина обох рядків однакова, тоді ми рухаємось далі, інакше ні, тому що рядки не можуть бути анаграмами, якщо їх довжини не схожий. Тож звідти ми повертаємо неправду.

Наступна наша логіка полягає в тому, щоб розташувати їх у порядку зростання, щоб кожен символ прийшов у порядок, тому ми визначили функцію “сортування”. Обидві рядки, які передаються у функцію сортування, перетворюються на тимчасовий масив, який збирається сортувати масив і повернути рядок у str1, тому відсортований рядок зберігається в одному рядку, це відбуватиметься з обома рядками, і ми отримуємо відсортовані рядки.

беззвучний = [s, i, l, e, n, t] // масив символів
listen = [l, i, s, t, e, n] // масив символів

відсортований масив = [e, i, l, n, s, t] // відсортований масив мовчазного, що зберігається в str1
відсортований масив = [e, i, l, n, s, t] // відсортований масив прослуховування, що зберігається в str2

Тоді за допомогою циклу for ми порівняємо кожен окремий індекс обох рядків, якщо однакові символи виявляться ідентичними, тоді вони є анаграмами і повертають істинний та “істинний” відбитки та помилкові відбитки, якщо він повертає false.

Реалізація

Програма C ++ для дійсних анаграм

#include <iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

bool areAnagram(string str1, string str2)
{
    //getting length of both the strings
    int n1 = str1.length();
    int n2 = str2.length();

    //Checking if both the strings are of same length
    if (n1 != n2)
        return false;

    //Sorting both the string alphabetically
    sort(str1.begin(), str1.end());
    sort(str2.begin(), str2.end());

    //checking each character of string is equal to
    //another character of string
    if (str1 != str2)
        return false;

    return true;
}

int main ()
{
    string str1 = "silent";
    string str2 = "listen";
    if(areAnagram(str1,str2))
        cout << "true";
    else
        cout << "false";
    return 0;
}
true

Програма Java для дійсних анаграм

import java.util.Arrays;
import java.util.Scanner;
class validAnagrams
{
  public static String sort(String str)
  {
      char temp[] = str.toCharArray();
      Arrays.sort(temp);
      return new String(temp);
  }
  public static boolean areAnagram(String str1, String str2)
  {
    //getting length of both the strings
    int length1 = str1.length();
    int length2 = str2.length();

    //Checking if both the strings are of same length
    if (length1 != length2)
    {
      return false;
    }

    //Sorting both the string alphabetically
    str1=sort(str1);
    str2=sort(str2);

    //checking each character of string is equal to
    //another character of string
    for (int i = 0; i < length1; i++)
    {
        if (str1.charAt(i) != str2.charAt(i))
        {
            return false;
      }
    }

        return true;
    }
  public static void main(String [] args)
  {
    String str1 = "silent";
    String str2 = "listen";
    System.out.println(areAnagram(str1,str2)?"true":"false");

  }
}
true

Аналіз складності для дійсних анаграм

Складність часу

O (nlogn) де n - розмір рядка. Тут ми сортуємо рядок на основі символу, який займає час nlogn.

Складність простору

O (1) тому що ми не використовуємо тут зайвого місця.