C++ में सरणी से पहला स्ट्रिंग जिसका उल्टा भी उसी सरणी में मौजूद हो

समस्या विवरण

इस समस्या में, हमें आकार N की स्ट्रिंग सरणी str[] दी गई है। हमारा कार्य दिए गए सरणी से पहला स्ट्रिंग खोजने के लिए एक प्रोग्राम बनाना है जिसका उल्टा भी उसी सरणी में मौजूद हो।

उदाहरण

इनपुट: str[] = ["python", "program", "C#", "language", "#C"]
आउटपुट: C#

हल का दृष्टिकोण

विधि 1: नेस्टेड लूप (O(N² × L))

समस्या को हल करने का एक तरीका स्ट्रिंग सरणी के प्रत्येक तत्व को सीधे पार करना और शेष सरणी में स्ट्रिंग के उल्टे की जांच करना है। यदि उल्टा मिल जाए तो स्ट्रिंग वापस करें। यदि पूरी सरणी पार हो गई और उल्टा मौजूद वाला कोई स्ट्रिंग नहीं मिला तो -1 वापस करें।

#include <iostream> 
#include <string> 
#include <algorithm> 
using namespace std; 

bool checkStringRev(string s1, string s2) {
    if (s1.length() != s2.length()) return false;
    int len = s1.length();
    for (int i = 0; i < len; i++)
        if (s1[i] != s2[len - i - 1]) return false;
    return true;
}

string checkRevStringArr(string strArr[], int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (checkStringRev(strArr[i], strArr[j]))
                return strArr[i];
    return "-1";
}

int main() {
    string strArr[] = {"python", "program", "C#", "language", "#C"};
    int n = sizeof(strArr) / sizeof(strArr[0]);
    cout << "सरणी से वह स्ट्रिंग जिसका उल्टा सरणी में मौजूद है: " 
         << checkRevStringArr(strArr, n);
    return 0;
}

विधि 2: हैशमैप (O(N × L)) - इष्टतम

एक और विधि जो रैखिक समय में यानी एकल पार में समस्या को हल कर सकती है, हैशमैप का उपयोग करना है। हम हैशमैप में प्रत्येक शब्द संग्रहीत करेंगे। यदि किसी स्ट्रिंग का उल्टा हैशमैप में मौजूद है तो हैशमैप से उल्टी स्ट्रिंग हमारा परिणाम है। और यदि पूरी सरणी में ऐसा कोई स्ट्रिंग नहीं है, तो -1 वापस करें।

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

string checkRevStringArr(string strArr[], int length) {
    unordered_map<string, bool> stringHashMap;
    
    for (int i = 0; i < length; i++) {
        string str = strArr[i];
        reverse(str.begin(), str.end());
        if (stringHashMap.find(str) != stringHashMap.end() && stringHashMap[str])
            return str;
        else
            stringHashMap[strArr[i]] = true;
    }
    return "-1";
}

int main() {
    string strArr[] = {"python", "program", "C#", "language", "#C"};
    int n = sizeof(strArr) / sizeof(strArr[0]);
    cout << "सरणी से वह स्ट्रिंग जिसका उल्टा सरणी में मौजूद है: " 
         << checkRevStringArr(strArr, n);
    return 0;
}

आउटपुट

सरणी से वह स्ट्रिंग जिसका उल्टा सरणी में मौजूद है: C#

जटिलता विश्लेषण

जहां L औसत स्ट्रिंग लंबाई है।