การสร้างคู่ Palindrome ในอาร์เรย์ของคำ (หรือสตริง) ใน C++

"มาดาม" หรือ "รถแข่ง" คือคำสองคำที่อ่านข้างหลังเหมือนไปข้างหน้า เรียกว่า palindromes

หากเราได้รับคอลเลกชั่นหรือรายการสตริง เราต้องเขียนโค้ด C++ เพื่อดูว่าสามารถรวมสองสตริงในรายการเข้าด้วยกันเพื่อสร้าง palindrome ได้หรือไม่ หากมีคู่ของสตริงดังกล่าวอยู่ในรายการที่กำหนด เราต้องพิมพ์ "ใช่" ไม่เช่นนั้น เราต้องพิมพ์ "ไม่ใช่"

ในบทช่วยสอนนี้ อินพุตจะเป็นอาร์เรย์ของสตริง และเอาต์พุตจะเป็นค่าสตริงตามลำดับ ตัวอย่างเช่น

ป้อนข้อมูล

list[] = {"flat", "tea", "chair", "ptalf", "tea"}

ผลผลิต

Yes

มีคู่ "แบน" และ "ptalf" ซึ่งสร้างสตริง palindrome "flatptalf"

ป้อนข้อมูล

list[] = {"raman", "ram", "na", "ar", "man"}

ผลผลิต

Yes

มีคู่ "na" และ "man" ซึ่งสร้างสตริง palindrome "naman"

แนวทางในการหาแนวทางแก้ไข

แนวทางกำลังดุร้าย

สำหรับแต่ละสตริงในอาร์เรย์ ให้ตรวจสอบสตริงอื่นๆ ทั้งหมดว่าสร้างพาลินโดรมกับสตริงอื่นหรือไม่ หากพบคู่ดังกล่าว ให้คืนค่า จริง หากองค์ประกอบอาร์เรย์ทั้งหมดถูกสำรวจเพื่อค้นหาคู่ดังกล่าว และไม่พบคู่ที่เหมาะสม ให้คืนค่าเท็จ

ความซับซ้อนของเวลา :O(N^2)

ความซับซ้อนของอวกาศ :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 < string > vect) {
   for (int i = 0; i < vect.size () - 1; i++) {
      for (int j = i + 1; j < vect.size (); j++) {
         string check_str = "";
         check_str = check_str + vect[i] + vect[j];
         if (isPalindrome (check_str))
            return true;
      }
   }
   return false;
}
int main () {
   vector < string > vect = { "flat", "tea", "chair", "ptalf", "tea"};
   checkPalindromePair (vect) ? cout << "Yes" : cout << "No";
   return 0;
}

ผลลัพธ์

Yes

แนวทางที่มีประสิทธิภาพหรือเหมาะสม

เราสามารถใช้โครงสร้างข้อมูลแบบทดลองเพื่อแก้ปัญหานี้ได้

ขั้นแรก เราต้องสร้าง trie ว่าง และสำหรับแต่ละสตริงในอาร์เรย์ เราต้องแทรกส่วนกลับของคำปัจจุบัน &เก็บว่าดัชนีใดเป็นพาลินโดรม จากนั้นเราต้องสำรวจอาร์เรย์อีกครั้ง และสำหรับแต่ละสตริง เราต้องทำสิ่งต่อไปนี้ -

• หากมีให้ใน True ให้คืนค่า true

• หากมีบางส่วน -- ตรวจสอบว่าคำที่เหลือคือ palindrome หรือไม่ ถ้าใช่ ให้คืนค่า จริง ซึ่งหมายความว่าคู่สร้าง palindrome

ความซับซ้อนของเวลา:O(Nk^2)

ความซับซ้อนของอวกาศ:O(N)

โดยที่ N คือจำนวนคำในรายการ และ k คือความยาวสูงสุดที่ตรวจสอบสำหรับ palindrome

ตัวอย่างที่ 2

#include<bits/stdc++.h>
using namespace std;
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define ALPHABET_SIZE (26)
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
struct TrieNode {
   struct TrieNode *children[ALPHABET_SIZE];
   vector < int >pos;
   int id;
   bool isLeaf;
};
struct TrieNode *
getNode (void) {
   struct 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 (struct TrieNode *root, string key, int id) {
   struct 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 (struct TrieNode *root, string key, int id,
vector < vector < int > >&result) {
   struct 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 < string > vect) {
   struct TrieNode *root = getNode ();
   for (int i = 0; i < vect.size (); i++)
   insert (root, vect[i], i);
   vector < vector < int >>result;
   for (int i = 0; i < vect.size (); i++) {
      search (root, vect[i], i, result);
      if (result.size () > 0) return true;
   }
   return false;
}
// Driver code int main () {
   vector < string > vect = { "flat", "tea", "chair", "ptalf", "tea"};
   checkPalindromePair (vect) ? cout << "Yes" : cout << "No";
   return 0;
}

ผลลัพธ์

Yes

บทสรุป

ในบทช่วยสอนนี้ เราได้เรียนรู้วิธีค้นหาคู่พาลินโดรมในอาร์เรย์ด้วยสองวิธี (Bruteforce และ Optimized) เรายังเขียนโค้ดนี้ในภาษาจาวา ไพธอน และภาษาอื่นๆ ได้ด้วย วิธีแรกคือวิธีพื้นฐานในการค้นหาวิธีแก้ปัญหาโดยสำรวจองค์ประกอบที่กำหนดทั้งหมด ในทางตรงกันข้าม วิธีที่สองใช้โครงสร้างข้อมูลแบบทดลองเพื่อให้คำตอบคือความซับซ้อนของเวลาเชิงเส้นเกือบ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์