İki ipin bir-birinin anaqramı olub olmadığını yoxlayın


SimBaxılıb 546

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

İki s1 və s2 sətri verildikdə, iki sətrin anaqram olub-olmadığını s2-nin s1 ilə eyni simvollar olduğu halda sXNUMX-nin anaqram olduğunu söyləyən bir funksiya yazın, lakin sıra fərqli ola bilər

Məsələn 1

INPUT
s1 = "abcd"
s2 = "cdbe"

ÇIXDI
Nəzərə alsaq ki, iki sətir bir-birinə anaqram deyildir, çünki s1 sətri bütün s2 simvollarını içərmir

Məsələn 2

s1 = “dərs fincanı”
s2 = “fincan təlimatı”

ÇIXDI
Verilən iki sim bir-birinə anaqramdır

Metod 1 (çeşidləmə istifadə edərək)

Zamanın mürəkkəbliyi: O (nlogn)

Alqoritm

1. Hər iki ipi də sıralayın

2. Sıralanmış simləri müqayisə edin

C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
 
//Prototype
void quickSort(char *arr, int start, int end);
int partition(char A[], int start, int end);
 
 
// It will swap two pointers
void swap(char *a, char *b)
{
    char temp;
    temp = *a;
    *a   = *b;
    *b   = temp;
}
//It will sort the given string
void quickSort(char S[], int start, int end)
{
    int pi;    // Partitioning index //
    if(start < end)
    {
        pi = partition(S, start, end);
        quickSort(S, start, pi - 1);
        quickSort(S, pi + 1, end);
    }
} 
int partition(char S[], int start, int end)
{
    char pivot = S[end];
    int i = (start - 1);
    int j;
 
    for (j = start; j <= end - 1; j++)
    {
        if(S[j] <= pivot)
        {
            i++;
            swap(&S[i], &S[j]);
        }
    }
    swap(&S[i + 1], &S[end]);
    return (i + 1);
}
 

// function to check whether two strings are anagram of 
// each other or not 
bool anagrams(char *s1, char *s2)
{
    // Get lenghts of both strings
    int m = strlen(s1);
    int n = strlen(s2);
 
    // If length of both strings is not same, then they 
    // cannot be anagram to each other
    if (m != n)
      return false;
 
    // Sort both strings
    quickSort(s1, 0, m - 1);
    quickSort(s2, 0, n - 1);
 
    // Compare sorted strings
    for (int i = 0; i < m;  i++)
       if (s1[i] != s2[i])
         return false;
 
    return true;
}
 
int main()
{
    char s1[] = "tutorial cup";
    char s2[] = "cup tutorial";
    if (anagrams(s1, s2))
    {
      cout<<"Given two strings are anagram to each other"<<endl;
    }
    else
    {
      cout<<"Given two strings are not anagram to each other"<<endl;
    }
 
    return 0;
}

Yoxla

Metod 2

Bu metodda əsas fikir hər iki simldəki simvolların meydana gəlməsini saymaq və onları müqayisə etməkdir

Alqoritm

1. S1 və s2 üçün iki say massivi yaradın.
yəni, məsələn 1
s1_count ['a'] = 1, s1_count ['b'] = 1, s1_count ['c'] = 1, s1_count ['d'] = 1.
s1_count ['c'] = 1, s1_count ['d'] = 1, s1_count ['b'] = 1, s2_count ['e'] = 1.

2. İki sayma massivini müqayisə edin.
yəni, məsələn 1
s1_count ['a'] = 1 s2__count ['a'] (0 olan) ilə uyğun gəlmir, buna görə də bir-birlərinin anagramı deyillər

C ++ Proqramı

# include <bits/stdc++.h>
# define NO_OF_CHARS 256

using namespace std;
 
//If the given strings are anagrams, returns true else false
bool anagrams(char *s1, char *s2)
{
    // Build count arrays for s1 and s2
    int s1_count[NO_OF_CHARS] = {0};
    int s2_count[NO_OF_CHARS] = {0};
    int i;
 
    // For each character in input strings, increment count in
    // the corresponding count array
    for (i = 0; s1[i] && s2[i];  i++)
    {
        s1_count[s1[i]]++;
        s2_count[s2[i]]++;
    }
 
    // If any of the two operands is non-zero, then condition becomes true.
    //If any string has more characters ie, s1 is "bfdd" and s2 is "bfd".
    //If the below condition is not present, the function says above s1 and s2 are anagrams
    //but, it is not true
    if (s1[i] || s2[i])
      return false;
 
    // Compare count arrays
    for (i = 0; i < NO_OF_CHARS; i++)
        if (s1_count[i] != s2_count[i])
            return false;
 
    return true;
}
 

int main()
{
    char s1[] = "abcde";
    char s2[] = "acdef";
    if (anagrams(s1, s2))
    {
      cout<<"Given two strings are anagram of each other"<<endl;
    }
    else
    {
      cout<<"The two strings are not anagram of each other"<<endl;
    }
 
    return 0;
}

Yoxla

 

Crack Sistemi Dizayn Müsahibələri
Translate »