ในปัญหานี้ เราได้รับอาร์เรย์ของสตริง str[] ขนาด N ภารกิจของเราคือ สร้างโปรแกรมหาสตริงแรกจากอาร์เรย์ที่กำหนดซึ่งสตริงย้อนกลับก็อยู่ในอาร์เรย์เดียวกัน
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input: str[] = ["python", "program", "C#", "language", "#C"] Output: C#
วิธีการแก้ปัญหา
วิธีหนึ่งในการแก้ปัญหาคือการเดินทางผ่านแต่ละองค์ประกอบของอาร์เรย์สตริงโดยตรงและตรวจสอบสตริงย้อนกลับในอาร์เรย์ที่เหลือ คืนค่าสตริง หากพบสตริงย้อนกลับ หากเดินทางผ่านอาร์เรย์ทั้งหมดและไม่พบสตริงที่มีสตริงย้อนกลับอยู่ ให้ คืนค่า -1
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#include<iostream> #include<string.h> 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<<"The string from the array whose reverse is present in the array is " <<checkRevStringArr(strArr, n); }
เอาต์พุต
The string from the array whose reverse is present in the array is C#
อีกวิธีหนึ่งที่สามารถแก้ปัญหาในเวลาเชิงเส้น คือการใช้ hashmap เราจะเก็บแต่ละคำใน hashmap หากสตริงใดมีสตริงย้อนกลับอยู่ใน hashmap แล้ว สตริงย้อนกลับจาก hashmap คือผลลัพธ์ของเรา และถ้าอาร์เรย์ทั้งหมดไม่มีสตริงแบบนั้น ให้คืนค่า -1
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#include<bits/stdc++.h> using namespace std; string checkRevStringArr(string strArr[], int length){ 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() and 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<<"The string from the array whose reverse is present in the array is "<<checkRevStringArr(strArr, n); }
เอาต์พุต
The string from the array whose reverse is present in the array is C#
