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

Input: arr[] =  {"geeksquiz", "geeksforgeeks", "abcd",
                 "forgeeksgeeks", "zuiqkeegs"};
Output: (geeksforgeeks, forgeeksgeeks), (geeksquiz, zuiqkeegs)

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

پیاده‌سازی رویکرد بالا در سی‌پلاس‌پلاس:

#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(string str1, string str2) 
{ 
    // Create two count arrays 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; 
} 
  
// This function prints all anagram pairs in a given array of strigns 
void findAllAnagrams(string arr[], int n) 
{ 
    for (int i = 0; i < n; i++) 
        for (int j = i+1; j < n; j++) 
            if (areAnagram(arr[i], arr[j])) 
                cout << arr[i] << " is anagram of " << arr[j] << endl; 
} 
  
  
/* Driver program to test to pront printDups*/
int main() 
{ 
    string arr[] = {"geeksquiz", "geeksforgeeks", "abcd",  
                    "forgeeksgeeks", "zuiqkeegs"}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    findAllAnagrams(arr, n); 
    return 0; 
}

پیاده‌سازی رویکرد بالا در جاوا:

// Java program to Print all pairs of  
// anagrams in a given array of strings 
public class GFG  
{ 
    static final int NO_OF_CHARS = 256; 
      
    /* function to check whether two  
    strings are anagram of each other */
    static boolean areAnagram(String str1, String str2) 
    { 
        // Create two count arrays and initialize 
        // all values as 0 
        int[] count = 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++) 
        { 
            count[str1.charAt(i)]++; 
            count[str2.charAt(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; 
  
        // See if there is any non-zero value in  
        // count array 
        for (i = 0; i < NO_OF_CHARS; i++) 
            if (count[i] != 0) 
                return false; 
         return true; 
    } 
  
    // This function prints all anagram pairs in a  
    // given array of strigns 
    static void findAllAnagrams(String arr[], int n) 
    { 
        for (int i = 0; i < n; i++) 
            for (int j = i+1; j < n; j++) 
                if (areAnagram(arr[i], arr[j])) 
                    System.out.println(arr[i] +  
                       " is anagram of " + arr[j]); 
    } 
  
    /* Driver program to test to pront printDups*/
    public static void main(String args[]) 
    { 
        String arr[] = {"geeksquiz", "geeksforgeeks", 
                        "abcd", "forgeeksgeeks",  
                        "zuiqkeegs"}; 
        int n = arr.length; 
        findAllAnagrams(arr, n); 
    } 
} 
// This code is contributed by Sumit Ghosh

پیاده‌سازی رویکرد بالا در سی‌شارپ:

// C# program to Print all pairs of  
// anagrams in a given array of strings 
using System; 
  
class GFG  
{ 
    static int NO_OF_CHARS = 256; 
      
    /* function to check whether two  
    strings are anagram of each other */
    static bool areAnagram(String str1, String str2) 
    { 
        // Create two count arrays and initialize 
        // all values as 0 
        int[] count = 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++) 
        { 
            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.Length != str2.Length) 
        return false; 
  
        // See if there is any non-zero value in  
        // count array 
        for (i = 0; i < NO_OF_CHARS; i++) 
            if (count[i] != 0) 
                return false; 
        return true; 
    } 
  
    // This function prints all anagram pairs in a  
    // given array of strigns 
    static void findAllAnagrams(String []arr, int n) 
    { 
        for (int i = 0; i < n; i++) 
            for (int j = i+1; j < n; j++) 
                if (areAnagram(arr[i], arr[j])) 
                    Console.WriteLine(arr[i] +  
                    " is anagram of " + arr[j]); 
    } 
  
    /* Driver program to test to pront printDups*/
    public static void Main() 
    { 
        String []arr = {"geeksquiz", "geeksforgeeks", 
                        "abcd", "forgeeksgeeks",  
                        "zuiqkeegs"}; 
        int n = arr.Length; 
        findAllAnagrams(arr, n); 
    } 
} 
  
// This code is contributed by nitin mittal

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

geeksquiz is anagram of zuiqkeegs
geeksforgeeks is anagram of forgeeksgeeks

پیچیدگی زمانی راهکار بالا از درجه O(n2*m)‎ است که در آن n تعداد رشته‌ها و m حداکثر طول یک رشته است. می‌توان راهکار بالا را با استفاده از رویکردهای ارائه شده در بخش بعدی مطلب، بهینه‌سازی کرد.

بهینه‌سازی

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

۱. استفاده از مرتب‌سازی: می‌توان آرایه رشته‌ها را مرتب‌سازی کرد تا همه آناگرام‌ها در کنار یکدیگر قرار بگیرند. سپس، همه آناگرام‌ها را با پیمایش خطی آرایه مرتب شده چاپ کرد. پیچیدگی زمانی این راهکار از درجه O(mnLogn)‎ است (مقایسه از درجه O(nLogn)‎ در مرتب‌سازی انجام می‌شود و مقایسه زمانی از درجه O(m) time‎ زمان می‌برد).

۲. استفاده از هش کردن: می‌توان یک تابع هش مانند XOR یا مجموع مقادیر اسکی از همه کاراکترها را برای یک رشته ساخت. با استفاده از چنین تابع هشی، می‌توان بررسی کرد که آیا مقادیر در حال حاضر هش شده‌اند یا خیر. در صورت مثبت بودن پاسخ، می‌توان همه areAnagrams()‎‌ها را برای بررسی اینکه آیا دو رشته آناگرام هستند یا نه فراخوانی کرد. (شایان ذکر است xor یا مجموع مقادیر ASCII مناسب نیستند).

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

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

منبع [+]