در این مطلب، هدف، نوشتن برنامه بررسی جناس قلب بودن دو رشته است. در واقع، قرار است تابعی نوشته شود که بررسی می‌کند آیا دو رشته داده شده (در ورودی) جناس قلب یکدیگر هستند یا خیر. جناس قلب یک رشته، رشته دیگری حاوی کاراکترهای مشابهی است و تنها ترتیب کاراکترها در آن تغییر پیدا کرده است. برای مثال، دو رشته «abcd» و «dabc» جناس قلب یکدیگر هستند.

راهکار اول برای پیاده‌سازی برنامه بررسی جناس قلب بودن دو رشته

روش اول برای بررسی جناس قلب بودن دو رشته، استفاده از مرتب‌سازی است. مراحل کلی این روش، در ادامه بیان شده‌اند.

1. مرتب‌سازی هر دو رشته
2. مقایسه رشته‌های مرتب شده

پیاده‌سازی راهکار اول در ++C

// C++ program to check whether two strings are anagrams 
// of each other 
#include <bits/stdc++.h> 
using namespace std; 
  
/* function to check whether two strings are anagram of  
each other */
bool areAnagram(string str1, string str2) 
{ 
    // Get lengths of both strings 
    int n1 = str1.length(); 
    int n2 = str2.length(); 
  
    // If length of both strings is not same, then they 
    // cannot be anagram 
    if (n1 != n2) 
        return false; 
  
    // Sort both the strings 
    sort(str1.begin(), str1.end()); 
    sort(str2.begin(), str2.end()); 
  
    // Compare sorted strings 
    for (int i = 0; i < n1; i++) 
        if (str1[i] != str2[i]) 
            return false; 
  
    return true; 
} 
  
// Driver code 
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 program to check whether two strings 
// are anagrams of each other 
import java.io.*; 
import java.util.Arrays; 
import java.util.Collections; 
  
class GFG { 
  
    /* function to check whether two strings are  
    anagram of each other */
    static boolean areAnagram(char[] str1, char[] str2) 
    { 
        // Get lenghts of both strings 
        int n1 = str1.length; 
        int n2 = str2.length; 
  
        // If length of both strings is not same, 
        // then they cannot be anagram 
        if (n1 != n2) 
            return false; 
  
        // Sort both strings 
        Arrays.sort(str1); 
        Arrays.sort(str2); 
  
        // Compare sorted strings 
        for (int i = 0; i < n1; i++) 
            if (str1[i] != str2[i]) 
                return false; 
  
        return true; 
    } 
  
    /* Driver program to test to print 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"); 
    } 
} 
  
// This code is contributed by Nikita Tiwari.

پیاده‌سازی راهکار اول در پایتون

# Python program to check whether two strings are  
# anagrams of each other  
  
# function to check whether two strings are anagram  
# of each other  
def areAnagram(str1, str2):  
    # Get lengths of both strings  
    n1 = len(str1)  
    n2 = len(str2)  
  
    # If lenght of both strings is not same, then  
    # they cannot be anagram  
    if n1 != n2:  
        return 0
  
    # Sort both strings  
    str1 = sorted(str1) 
    str2 = sorted(str2) 
  
    # Compare sorted strings  
    for i in range(0, n1):  
        if str1[i] != str2[i]:  
            return 0
  
    return 1
  
  
# Driver program to test the above function  
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") 
  
# This code is contributed by Bhavya Jain

پیاده‌سازی راهکار بالا در #C

// C# program to check whether two 
// strings are anagrams of each other 
using System; 
using System.Collections; 
class GFG { 
  
    /* function to check whether two  
strings are anagram of each other */
    public static bool areAnagram(ArrayList str1, 
                                  ArrayList str2) 
    { 
        // Get lenghts of both strings 
        int n1 = str1.Count; 
        int n2 = str2.Count; 
  
        // If length of both strings is not 
        // same, then they cannot be anagram 
        if (n1 != n2) { 
            return false; 
        } 
  
        // Sort both strings 
        str1.Sort(); 
        str2.Sort(); 
  
        // Compare sorted strings 
        for (int i = 0; i < n1; i++) { 
            if (str1[i] != str2[i]) { 
                return false; 
            } 
        } 
  
        return true; 
    } 
  
    // Driver Code 
    public static void Main(string[] args) 
    { 
        // create and initalize new ArrayList 
        ArrayList str1 = new ArrayList(); 
        str1.Add('t'); 
        str1.Add('e');https://www.youtube.com/watch?v=Tztc73r8348 
        str1.Add('s'); 
        str1.Add('t'); 
        // create and initalize new 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"); 
        } 
    } 
} 
  
// This code is contributed by Shrikant13

خروجی قطعه کدهای بالا، به صورت زیر است.

The two strings are not anagram of each other

پیچیدگی زمانی راهکار ارائه شده در بالا، از درجه O(nLogn)‎ است.

راهکار دوم برای پیاده‌سازی برنامه بررسی جناس قلب بودن دو رشته

در این روش فرض بر این است که مجموعه کاراکترهای ممکن در هر دو رشته، کوچک هستند. در پیاده‌سازی که در ادامه می‌آید، فرض بر آن است که کاراکترها با استفاده از ۸ بیت ذخیره شده‌اند و در کل می‌تواند ۲۵۶ حالت کاراکتر وجود داشته باشد. مراحل این روش، در ادامه بیان شده‌اند.

1. ساخت آرایه‌های شمارشی با اندازه ۲۵۶ برای هر دو رشته. مقداردهی اولیه همه مقادیر در آرایه شمارشی به عنوان صفر
2. تکرار در هر کاراکتر از دو رشته و افزایش شمارش کاراکترها در آرایه‌های شمارشی متناظر
3. مقایسه آرایه‌های شمارشی؛ اگر هر دو آرایه شمارشی مشابه هستند، مقدار true را بازگردان.

پیاده‌سازی راهکار دوم در ++C

// C++ program to check if two strings 
// are anagrams of each other 
#include <bits/stdc++.h> 
using namespace std; 
#define NO_OF_CHARS 256 
  
/* function to check whether two strings are anagram of  
each other */
bool areAnagram(char* str1, char* str2) 
{ 
    // Create 2 count arrays and initialize all values as 0 
    int count1[NO_OF_CHARS] = { 0 }; 
    int count2[NO_OF_CHARS] = { 0 }; 
    int i; 
  
    // For each character in input strings, increment count in 
    // the corresponding count array 
    for (i = 0; str1[i] && str2[i]; i++) { 
        count1[str1[i]]++; 
        count2[str2[i]]++; 
    } 
  
    // If both strings are of different length. Removing this 
    // condition will make the program fail for strings like 
    // "aaca" and "aca" 
    if (str1[i] || str2[i]) 
        return false; 
  
    // Compare count arrays 
    for (i = 0; i < NO_OF_CHARS; i++) 
        if (count1[i] != count2[i]) 
            return false; 
  
    return true; 
} 
  
/* Driver code*/
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; 
} 
  
// This is code is contributed by rathbhupendra

پیاده‌سازی راهکار دوم در C

// C program to check if two strings 
// are anagrams of each other 
#include <stdio.h> 
#define NO_OF_CHARS 256 
  
/* function to check whether two strings are anagram of  
   each other */
bool areAnagram(char* str1, char* str2) 
{ 
    // Create 2 count arrays and initialize all values as 0 
    int count1[NO_OF_CHARS] = { 0 }; 
    int count2[NO_OF_CHARS] = { 0 }; 
    int i; 
  
    // For each character in input strings, increment count in 
    // the corresponding count array 
    for (i = 0; str1[i] && str2[i]; i++) { 
        count1[str1[i]]++; 
        count2[str2[i]]++; 
    } 
  
    // If both strings are of different length. Removing this 
    // condition will make the program fail for strings like 
    // "aaca" and "aca" 
    if (str1[i] || str2[i]) 
        return false; 
  
    // Compare count arrays 
    for (i = 0; i < NO_OF_CHARS; i++) 
        if (count1[i] != count2[i]) 
            return false; 
  
    return true; 
} 
  
/* Driver program to test to print 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 program to check if two strings 
// are anagrams of each other 
import java.io.*; 
import java.util.*; 
  
class GFG { 
  
    static int NO_OF_CHARS = 256; 
  
    /* function to check whether two strings 
    are anagram of each other */
    static boolean areAnagram(char str1[], char str2[]) 
    { 
        // Create 2 count arrays and initialize 
        // all values as 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 each character in input strings, 
        // increment count in the corresponding 
        // count array 
        for (i = 0; i < str1.length && i < str2.length; 
             i++) { 
            count1[str1[i]]++; 
            count2[str2[i]]++; 
        } 
  
        // If both strings are of different length. 
        // Removing this condition will make the program 
        // fail for strings like "aaca" and "aca" 
        if (str1.length != str2.length) 
            return false; 
  
        // Compare count arrays 
        for (i = 0; i < NO_OF_CHARS; i++) 
            if (count1[i] != count2[i]) 
                return false; 
  
        return true; 
    } 
  
    /* Driver program to test to print 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"); 
    } 
} 
  
// This code is contributed by Nikita Tiwari.

پیاده‌سازی راهکار دوم در پایتون

# Python program to check if two strings are anagrams of 
# each other 
NO_OF_CHARS = 256
  
# Function to check whether two strings are anagram of 
# each other 
def areAnagram(str1, str2): 
  
    # Create two count arrays and initialize all values as 0 
    count1 = [0] * NO_OF_CHARS 
    count2 = [0] * NO_OF_CHARS 
  
    # For each character in input strings, increment count 
    # in the corresponding count array 
    for i in str1: 
        count1[ord(i)]+= 1
  
    for i in str2: 
        count2[ord(i)]+= 1
  
    # If both strings are of different length. Removing this 
    # condition will make the program fail for strings like 
    # "aaca" and "aca" 
    if len(str1) != len(str2): 
        return 0
  
    # Compare count arrays 
    for i in xrange(NO_OF_CHARS): 
        if count1[i] != count2[i]: 
            return 0
  
    return 1
  
# Driver program to test the above functions 
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"
  
# This code is contributed by Bhavya Jain

پیاده‌سازی راهکار دوم در #C

// C# program to check if two strings 
// are anagrams of each other 
  
using System; 
  
public class GFG { 
  
    static int NO_OF_CHARS = 256; 
  
    /* function to check whether two strings 
    are anagram of each other */
    static bool areAnagram(char[] str1, char[] str2) 
    { 
        // Create 2 count arrays and initialize 
        // all values as 0 
        int[] count1 = new int[NO_OF_CHARS]; 
        int[] count2 = new int[NO_OF_CHARS]; 
        int i; 
  
        // For each character in input strings, 
        // increment count in the corresponding 
        // count array 
        for (i = 0; i < str1.Length && i < str2.Length; 
             i++) { 
            count1[str1[i]]++; 
            count2[str2[i]]++; 
        } 
  
        // If both strings are of different length. 
        // Removing this condition will make the program 
        // fail for strings like "aaca" and "aca" 
        if (str1.Length != str2.Length) 
            return false; 
  
        // Compare count arrays 
        for (i = 0; i < NO_OF_CHARS; i++) 
            if (count1[i] != count2[i]) 
                return false; 
  
        return true; 
    } 
  
    /* Driver program to test to print 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"); 
    } 
} 
  
// This code contributed by 29AjayKumar

خروجی قطعه کد بالا، به صورت زیر است.

The two strings are anagram of each other

راهکار سوم برای پیاده‌سازی برنامه بررسی جناس قلب بودن دو رشته

در این روش، محاسبه کاراکترها با استفاده از یک آرایه انجام می‌شود. در واقع، پیاده‌سازی بالا را می‌توان به گونه‌ای تغییر داد که به جای استفاده از دو آرایه، از یک آرایه استفاده شود. می‌توان مقدار در آرایه شمارشی را برای کاراکترها در str1 افزایش داد و مستندات برای کاراکترها در str2 را کاهش داد. در نهایت، اگر همه مقادیر شمارشی برابر با صفر باشند، دو رشته آناگرام یکدیگر هستند (جناس قلب). پیاده‌سازی این روش، به صورت زیر است.

bool areAnagram(char* str1, char* str2) 
{ 
    // Create a count array and initialize all values as 0 
    int count[NO_OF_CHARS] = { 0 }; 
    int i; 
  
    // For each character in input strings, increment count in 
    // the corresponding count array 
    for (i = 0; str1[i] && str2[i]; i++) { 
        count[str1[i]]++; 
        count[str2[i]]--; 
    } 
  
    // If both strings are of different length. Removing this condition 
    // will make the program fail for strings like "aaca" and "aca" 
    if (str1[i] || str2[i]) 
        return false; 
  
    // See if there is any non-zero value in count array 
    for (i = 0; i < NO_OF_CHARS; i++) 
        if (count[i]) 
            return false; 
    return true; 
}

اگر مجموعه ممکن از کاراکترها تنها حاوی الفبای انگلیسی باشد، می‌توان سایز آرایه را به ۵۲ کاهش داد و از str[i] – ‘A’ ‎ به عنوان اندیس برای آرایه شمارشی استفاده کرد. این کار موجب می‌شود که این روش، بیش از پیش بهینه شود. پیچیدگی زمانی این روش، از درجه O(n)‎ است. 

راهکار چهارم برای پیاده‌سازی برنامه بررسی جناس قلب بودن دو رشته

در این روش، از دستکاری بیت‌ها استفاده می‌شود. پیاده‌سازی بالا را می‌توان با استفاده از دستکاری بیت‌ها، بیش از پیش بهینه‌سازی کرد. اگر کار با مقدار ۰ شروع شود و همه کاراکترهای هر دو رشته با یکدیگر XOR شوند، در صورتی که رشته‌ها جناس قلب (آناگرام) باشند، یک مقدار پایانی ۰ بازگردانده می‌شود؛ زیرا همه کاراکترها به طور یکنواخت در آناگرام خواهند بود.

پیاده‌سازی راهکار چهارم در ++C

// C++ program to check if two strings 
// are anagrams of each other 
#include <bits/stdc++.h> 
using namespace std; 
   
// Function to check whether two strings are anagram of  
// each other  
bool areAnagram(string str1, string str2) 
{ 
    // If two strings have different size 
    if (str1.size() != str2.size()) { 
        return false; 
    } 
   
    // To store the xor value 
    int value = 0; 
   
    for (int i = 0; i < str1.size(); i++) { 
        value = value ^ (int) str1[i]; 
        value = value ^ (int) str2[i]; 
    } 
   
    return value == 0; 
   
} 
   
// Driver code 
int main() 
{ 
    string str1 = "geeksforgeeks"; 
    string 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; 
}

پیاده‌سازی راهکار چهارم در جاوا

// Java program to check if two strings  
// are anagrams of each other  
class GFG 
{ 
  
// Function to check whether two strings are anagram of  
// each other  
static boolean areAnagram(String str1, String str2)  
{  
    // If two strings have different length  
    if (str1.length() != str2.length())  
    {  
        return false;  
    }  
  
    // To store the xor value  
    int value = 0;  
  
    for (int i = 0; i < str1.length(); i++)  
    {  
        value = value ^ (int) str1.charAt(i);  
        value = value ^ (int) str2.charAt(i);  
    }  
  
    return value == 0;  
  
}  
  
// Driver code  
public static void main(String[] args)  
{ 
    String str1 = "geeksforgeeks";  
    String str2 = "forgeeksgeeks";  
    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");  
  
} 
} 
  
// This code is contributed by 29AjayKumar

پیاده‌سازی رویکرد چهارم در پایتون ۳

# Python program to check if two strings 
# are anagrams of each other 
  
# Function to check whether two strings are anagram of  
# each other  
def areAnagram(str1, str2): 
      
    # If two strings have different size 
    if (len(str1) != len(str2)): 
        return False; 
  
    # To store the xor value 
    value = 0; 
  
    for i in range(0,len(str1)): 
        value = value ^ ord(str1[i]); 
        value = value ^ ord(str2[i]); 
  
    return value == 0; 
  
# Driver code 
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"); 
  
# This code is contributed by Rajput-Ji

پیاده‌سازی راهکار چهارم در #C

// C# program to check if two strings  
// are anagrams of each other  
using System; 
  
class GFG 
{ 
      
// Function to check whether two strings are anagram of  
// each other  
static bool areAnagram(String str1, String str2)  
{  
    // If two strings have different length  
    if (str1.Length != str2.Length)  
    {  
        return false;  
    }  
  
    // To store the xor value  
    int value = 0;  
  
    for (int i = 0; i < str1.Length; i++)  
    {  
        value = value ^ (int) str1[i];  
        value = value ^ (int) str2[i];  
    }  
  
    return value == 0;  
  
}  
  
// Driver code 
static public void Main () 
{ 
      
    String str1 = "geeksforgeeks";  
    String str2 = "forgeeksgeeks";  
    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");  
  
} 
} 
  
// This code is contributed by ajit.

خروجی قطعه کدهای بالا به صورت زیر است.

The two strings are anagram of each other

پیچیدگی زمانی این روش از درجه O(n)‎ و پیچیدگی فضایی آن از درجه است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده
• الگوریتم جست و جوی دودویی در جاوا اسکریپت — به زبان ساده

منبع [+]