"Madam" หรือ "racecar" เป็นคำสองคำที่อ่านจากหน้าหลังและหลังหน้าได้เหมือนกัน เรียกว่า พาลินโดรม (Palindrome)
หากเราได้รับชุดหรือรายการสตริง เราต้องเขียนโค้ด C++ เพื่อหาว่าสามารถนำสตริงสองตัวในรายการมาต่อกันได้เป็นพาลินโดรมหรือไม่ หากมีคู่ดังกล่าวอยู่ในรายการที่ให้มา เราต้องพิมพ์ "Yes" มิฉะนั้นพิมพ์ "No"
ในบทช่วยสอนนี้ ข้อมูลนำเข้าจะเป็นอาร์เรย์ของสตริง และข้อมูลส่งออกจะเป็นค่าสตริงตามลำดับ เช่น
ข้อมูลนำเข้า
list[] = {"flat", "tea", "chair", "ptalf", "tea"}
ข้อมูลส่งออก
Yes
มีคู่ "flat" และ "ptalf" ซึ่งรวมกันเป็นสตริงพาลินโดรม "flatptalf"
ข้อมูลนำเข้า
list[] = {"raman", "ram", "na", "ar", "man"}
ข้อมูลส่งออก
Yes
มีคู่ "na" และ "man" ซึ่งรวมกันเป็นสตริงพาลินโดรม "naman"
แนวทางการหาคำตอบ
วิธี Brute Force (ลองทุกคู่)
สำหรับแต่ละสตริงในอาร์เรย์ ตรวจสอบสตริงอื่นทั้งหมดว่ารวมกันเป็นพาลินโดรมได้หรือไม่ หากพบคู่ดังกล่าว คืนค่า true หากตรวจสอบทุกองค์ประกอบแล้วไม่พบคู่ที่เหมาะสม คืนค่า false
Time Complexity: O(N^2)
Space Complexity: O(1)
ตัวอย่างโค้ด (Brute Force)
#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
วิธีที่มีประสิทธิภาพ (Optimized)
เราสามารถใช้โครงสร้างข้อมูล Trie เพื่อแก้ปัญหานี้ได้
ขั้นแรก สร้าง Trie ว่าง สำหรับแต่ละสตริงในอาร์เรย์ ให้แทรกคำกลับ (reverse) ของคำปัจจุบัน และเก็บดัชนีที่เป็นพาลินโดรมจนถึงตำแหน่งนั้น แล้วเดินทางอาร์เรย์อีกครั้ง สำหรับแต่ละสตริง ทำดังนี้:
- หากพบใน Trie แล้ว คืนค่า true
- หากพบบางส่วน — ตรวจสอบคำที่เหลือเป็นพาลินโดรมหรือไม่ ถ้าใช่ คืนค่า true หมายถึงมีคู่ที่รวมเป็นพาลินโดรม
Time Complexity: O(Nk^2)
Space Complexity: O(N)
โดย N คือจำนวนคำในรายการ และ k คือความยาวสูงสุดที่ตรวจสอบพาลินโดรม
ตัวอย่างโค้ด (วิธี Optimized)
#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
สรุป
ในบทช่วยสอนนี้ เราเรียนรู้วิธีหาคู่พาลินโดรมในอาร์เรย์ด้วยสองวิธี (Brute Force และ Optimized) สามารถเขียนใน Java, Python และภาษาอื่นๆ ได้ วิธีแรกเป็นวิธีพื้นฐานในการหาคำตอบโดยการท่องทุกองค์ประกอบ ในขณะที่วิธีที่สองใช้โครงสร้างข้อมูล Trie ทำให้ได้คำตอบในเวลาเกือบเส้นตรง หวังว่าบทช่วยสอนนี้จะมีประโยชน์
