数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在C++中创建单词（或字符串）数组中的回文对
“Madam”或“racecar”是两个正反读都一样的单词，称为回文。
如果给定一个字符串集合或列表，我们需要编写一个C++代码来找出是否可以将列表中的任意两个字符串连接在一起形成回文。如果给定列表中存在这样的字符串对，则需要打印“Yes”，否则需要打印“No”。
在本教程中，输入将是一个字符串数组，输出将是相应的字符串值，例如
输入
list[] = {"flat", "tea", "chair", "ptalf", "tea"}输出
Yes
存在一对“flat”和“ptalf”，它们构成回文字符串“flatptalf”。
输入
list[] = {"raman", "ram", "na", "ar", "man"}输出
Yes
存在一对“na”和“man”，它们构成回文字符串“naman”。
查找解决方案的方法
暴力法
对于数组中的每个字符串，检查所有其他字符串是否与任何其他字符串一起形成回文。如果找到这样的对，则返回true。如果遍历了所有数组元素来搜索这样的对，并且没有找到合适的对，则返回false。
时间复杂度：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数据结构来解决这个问题。
首先，我们需要创建一个空的Trie，对于数组中的每个字符串，我们需要插入当前单词的反向，并存储它是回文到哪个索引。然后，我们需要再次遍历数组，对于每个字符串，我们需要执行以下操作：
如果它在True中可用，则返回true
如果它部分可用——检查剩余的单词是否是回文。如果是，则返回true，这意味着一个对形成了回文。
时间复杂度：O(Nk^2)
空间复杂度：O(N)
其中N是列表中的单词数，k是检查回文的最大长度。
示例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
结论
在本教程中，我们学习了如何使用两种方法（暴力法和优化方法）在数组中查找回文对。我们也可以用Java、Python和其他语言编写这段代码。第一种方法是通过遍历所有给定元素来查找任何解决方案的基本方法。相比之下，第二种方法使用Trie数据结构，因此它可以在几乎线性的时间复杂度内给出答案。我们希望您觉得本教程有所帮助。
450 次浏览
