"Madam" hoặc "racecar" là hai từ đọc giống nhau từ trái sang phải và từ phải sang trái, được gọi là palindrome.
Nếu chúng ta được cho một tập hợp hoặc danh sách các chuỗi, chúng ta phải viết code C++ để tìm xem có thể nối bất kỳ hai chuỗi nào trong danh sách lại với nhau để tạo thành một palindrome hay không. Nếu tồn tại cặp chuỗi như vậy trong danh sách cho trước, chúng ta phải in "Yes", ngược lại in "No".
Trong hướng dẫn này, đầu vào sẽ là một mảng các chuỗi, và đầu ra sẽ là một giá trị chuỗi tương ứng, ví dụ:
Đầu vào
list[] = {"flat", "tea", "chair", "ptalf", "tea"}Đầu ra
Yes
Có cặp "flat" và "ptalf" tạo thành chuỗi palindrome "flatptalf".
Đầu vào
list[] = {"raman", "ram", "na", "ar", "man"}Đầu ra
Yes
Có cặp "na" và "man" tạo thành chuỗi palindrome "naman".
Cách tiếp cận để tìm giải pháp
Cách tiếp cận Brute Force
Với mỗi chuỗi trong mảng, kiểm tra tất cả các chuỗi khác xem nó có tạo thành palindrome với chuỗi nào khác hay không. Nếu tìm thấy cặp như vậy, trả về true. Nếu tất cả các phần tử mảng đều được duyệt để tìm cặp như vậy và không tìm thấy cặp phù hợp, trả về false.
Độ phức tạp thời gian: O(N^2)
Độ phức tạp không gian: O(1)
Ví dụ
#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; }Đầu ra
Yes
Cách tiếp cận Hiệu quả hoặc Tối ưu
Chúng ta có thể sử dụng cấu trúc dữ liệu trie để giải quyết bài toán này.
Đầu tiên, chúng ta phải tạo một trie rỗng, và với mỗi chuỗi trong mảng, chúng ta phải chèn ngược của từ hiện tại & cũng lưu trữ đến chỉ số nào nó là palindrome. Sau đó chúng ta phải duyệt mảng lần nữa, và với mỗi chuỗi, chúng ta phải làm như sau:
Nếu nó có sẵn trong True, thì trả về true
Nếu nó có một phần --Kiểm tra từ còn lại có phải palindrome hay không Nếu có, thì trả về true nghĩa là một cặp tạo thành palindrome.
Độ phức tạp thời gian: O(Nk^2)
Độ phức tạp không gian: O(N)
Nơi N là số từ trong danh sách và k là độ dài tối đa được kiểm tra cho palindrome.
Ví dụ 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; }Đầu ra
Yes
Kết luận
Trong hướng dẫn này, chúng ta đã học cách tìm cặp palindrome trong mảng với hai cách tiếp cận (Brute Force và Tối ưu). Chúng ta cũng có thể viết code này bằng Java, Python và các ngôn ngữ khác. Cách tiếp cận đầu tiên là cách cơ bản để tìm bất kỳ giải pháp nào bằng cách duyệt tất cả các phần tử cho trước. Ngược lại, cách tiếp cận thứ hai sử dụng cấu trúc dữ liệu trie để đưa ra câu trả lời với độ phức tạp thời gian gần như tuyến tính. Hy vọng bạn thấy hướng dẫn này hữu ích.