"Madam" hoặc "racecar" là hai từ đọc ngược lại như sau, được gọi là palindromes.
Nếu chúng ta được cung cấp một tập hợp hoặc danh sách các chuỗi, chúng ta phải viết mã C ++ để tìm xem liệu chuỗi đó có thể nối hai chuỗi bất kỳ trong danh sách với nhau để tạo thành một palindrome hay không. Nếu bất kỳ cặp chuỗi nào như vậy tồn tại trong danh sách đã cho, chúng ta phải in "Có", nếu không, chúng ta phải in "Không"
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ó một cặp "phẳng" và "ptalf" tạo thành chuỗi palindrome "flatptalf".
Đầu vào
list[] = {"raman", "ram", "na", "ar", "man"} Đầu ra
Yes
Có một cặp "na" và "man" tạo thành chuỗi palindrome "naman".
Phương pháp tiếp cận để tìm giải pháp
Phương pháp tiếp cận vũ phu
Đối với mỗi chuỗi trong mảng, hãy kiểm tra tất cả các chuỗi khác xem nó có tạo thành palindrome với bất kỳ chuỗi nào khác hay không. Nếu một cặp như vậy được tìm thấy, trả về true. Nếu tất cả các phần tử của mảng được duyệt qua để tìm kiếm một cặp như vậy và không tìm thấy cặp nào phù hợp, hãy trả về false.
Độ phức tạp về thời gian:O (N ^ 2)
Độ phức tạp của 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
Phương pháp tiếp cận hiệu quả hoặc tối ưu hóa
Chúng tôi có thể sử dụng cấu trúc dữ liệu trie để giải quyết vấn đề này.
Đầu tiên, chúng ta phải tạo một trie trống và đối với mỗi chuỗi trong mảng, chúng ta phải chèn phần ngược lại của từ hiện tại và cũng lưu trữ nó là palindrome ở chỉ mục nào. Sau đó, chúng ta phải duyệt lại mảng và đối với mỗi chuỗi, chúng ta phải thực hiện như sau-
-
Nếu nó có sẵn ở dạng True, thì trả về true
-
Nếu nó có sẵn một phần - Kiểm tra từ còn lại có phải là 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 về thời gian:O (Nk ^ 2)
Độ phức tạp về không gian:O (N)
Trong đó 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 một cặp palindrome trong một mảng với hai cách tiếp cận (Bruteforce và Optimized). Chúng tôi cũng có thể viết mã này bằng java, python và các ngôn ngữ khác. Cách tiếp cận đầu tiên là một cách cơ bản để tìm ra bất kỳ giải pháp nào bằng cách duyệt qua tất cả các yếu tố đã cho. 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 là độ phức tạp thời gian gần như tuyến tính. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.