C++-এ শব্দের অ্যারেতে প্যালিনড্রোম জোড়া খুঁজে বের করা

"Madam" বা "racecar"처럼 উল্টে পড়লেও একই পড়া শব্দকে প্যালিনড্রোম বলে। একটি স্ট্রিং অ্যারে দেওয়া থাকলে, কোনো দুটি শব্দ জোড়া করে প্যালিনড্রোম বানানো যায় কিনা তা চেক করতে হবে। পার্ল হলে "Yes", না হলে "No" প্রিন্ট করতে হবে।

ইনপুট/আউটপুট উদাহরণ

ইনপুট: list[] = {"flat", "tea", "chair", "ptalf", "tea"}
আউটপুট: Yes (কারণ "flat" + "ptalf" = "flatptalf" প্যালিনড্রোম)

ইনপুট: list[] = {"raman", "ram", "na", "ar", "man"}
আউটপুট: Yes (কারণ "na" + "man" = "naman" প্যালিনড্রোম)

সমাধানের পদ্ধতি

ব্রুট ফোর্স পদ্ধতি

প্রতিটি স্ট্রিংয়ের সাথে বাকি সব স্ট্রিং চেক করুন। প্যালিনড্রোম পেলে true রিটার্ন করুন। টাইম কমপ্লেক্সিটি: O(N²×k), স্পেস: O(1)।

উদাহরণ ১ (ব্রুট ফোর্স)

#include <bits/stdc++.h> 
using namespace std; 

bool isPalindrome(string str) { 
    int len = str.length(); 
    for (int i = 0; i < len / 2; i++) 
        if (str[i] != str[len - i - 1]) return false; 
    return true; 
} 

bool checkPalindromePair(vector vect) { 
    for (int i = 0; i < vect.size() - 1; i++) { 
        for (int j = i + 1; j < vect.size(); j++) { 
            string check_str = vect[i] + vect[j]; 
            if (isPalindrome(check_str)) return true; 
        } 
    } 
    return false; 
} 

int main() { 
    vector vect = {"flat", "tea", "chair", "ptalf", "tea"}; 
    checkPalindromePair(vect) ? cout << "Yes" : cout << "No"; 
    return 0; 
}

আউটপুট

Yes

অপ্টিমাইজড পদ্ধতি (ট্রাই ডেটা স্ট্রাকচার)

ট্রাই ব্যবহার করে সমাধান করা যায়। প্রতিটি শব্দের রিভার্স ট্রাই-তে ইনসার্ট করুন এবং প্যালিনড্রোম প্রিফিক্স ট্র্যাক করুন। তারপর প্রতিটি শব্দের জন্য ট্রাই-তে সার্চ করুন। টাইম: O(N×k²), স্পেস: O(N)।

উদাহরণ ২ (ট্রাই)

#include <bits/stdc++.h> 
using namespace std; 

#define ALPHABET_SIZE 26 
#define CHAR_TO_INDEX(c) ((int)c - (int)'a') 

struct TrieNode { 
    TrieNode* children[ALPHABET_SIZE]; 
    vector pos; 
    int id; 
    bool isLeaf; 
}; 

TrieNode* getNode() { 
    TrieNode* pNode = new TrieNode; 
    pNode->isLeaf = false; 
    for (int i = 0; i < ALPHABET_SIZE; i++) pNode->children[i] = NULL; 
    return pNode; 
} 

bool isPalindrome(string str, int i, int len) { 
    while (i < len) { 
        if (str[i] != str[len]) return false; 
        i++; len--; 
    } 
    return true; 
} 

void insert(TrieNode* root, string key, int id) { 
    TrieNode* pCrawl = root; 
    for (int level = key.length() - 1; level >= 0; level--) { 
        int index = CHAR_TO_INDEX(key[level]); 
        if (!pCrawl->children[index]) pCrawl->children[index] = getNode(); 
        if (isPalindrome(key, 0, level)) pCrawl->pos.push_back(id); 
        pCrawl = pCrawl->children[index]; 
    } 
    pCrawl->id = id; 
    pCrawl->pos.push_back(id); 
    pCrawl->isLeaf = true; 
} 

void search(TrieNode* root, string key, int id, vector>& result) { 
    TrieNode* pCrawl = root; 
    for (int level = 0; level < key.length(); level++) { 
        int index = CHAR_TO_INDEX(key[level]); 
        if (pCrawl->id >= 0 && pCrawl->id != id && isPalindrome(key, level, key.size() - 1)) 
            result.push_back({id, pCrawl->id}); 
        if (!pCrawl->children[index]) return; 
        pCrawl = pCrawl->children[index]; 
    } 
    for (int i : pCrawl->pos) { 
        if (i == id) continue; 
        result.push_back({id, i}); 
    } 
} 

bool checkPalindromePair(vector vect) { 
    TrieNode* root = getNode(); 
    for (int i = 0; i < vect.size(); i++) insert(root, vect[i], i); 
    vector> result; 
    for (int i = 0; i < vect.size(); i++) { 
        search(root, vect[i], i, result); 
        if (result.size() > 0) return true; 
    } 
    return false; 
} 

int main() { 
    vector vect = {"flat", "tea", "chair", "ptalf", "tea"}; 
    checkPalindromePair(vect) ? cout << "Yes" : cout << "No"; 
    return 0; 
}

আউটপুট

Yes

উপসংহার

দুটি পদ্ধতিতে প্যালিনড্রোম জোড়া খুঁজে বের করা শেখানো হয়েছে: ব্রুট ফোর্স এবং ট্রাই-ভিত্তিক অপ্টিমাইজড পদ্ধতি।