Жарамды анаграммалар


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Голдман Сакс Google Microsoft Нагарро
Анаграмма Хэш

«Жарамды анаграммалар» деген есепте біз екеуін келтірдік жолдар str1 және str2. Екі ішектің де анаграмма екенін немесе жоқ екенін анықтаңыз. Егер олар болса анаграммалар return true else жалғанға қайтару.

мысал

Кіру:

str1 = «abcbac»

str2 = «aabbcc»

Шығару:

шынайы

Түсіндіру:

Str2 барлық стр сөздерін қайта құру арқылы жасалуы мүмкін болғандықтан, нәтиже шығады «шын ».

Алгоритм

  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 циклімен екі жолдың әрбір жеке индексін салыстырамыз, егер бірдей символдар бірдей деп табылса, онда олар анаграмма болып табылады және егер true және «true» басылымдары және жалған қайтарылса, жалған басып шығарады.

Іске асыру

Жарамды анаграммаларға арналған 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) өйткені біз бұл жерде артық орынды қолданбаймыз.