在 C++ 中的单词（或字符串）数组中创建回文对

“女士”或“赛车”是两个前后读相同的词，称为回文。

如果给定一个字符串集合或列表，我们必须编写一个 C++ 代码来确定它是否可以将列表中的任何两个字符串连接在一起以形成回文。如果给定列表中存在任何这样的字符串对，我们必须打印“是”，否则我们必须打印“否”。

在本教程中，输入将是一个字符串数组，输出将是相应的字符串值，例如

输入

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;
}
//驱动代码 int main () {
   vector < string > vect = { "flat", "tea", "chair", "ptalf", "tea"};
   checkPalindromePair (vect) ? cout << "Yes" : cout << "No";
   return 0;
}

输出结果

Yes

结论

在本教程中，我们学习了如何使用两种方法（Bruteforce 和 Optimized）在数组中查找回文对。我们也可以用 java、python 和其他语言编写此代码。第一种方法是通过遍历所有给定元素来找到任何解决方案的基本方法。相比之下，第二种方法使用 trie 数据结构，因此它给出的答案几乎是线性时间复杂度。我们希望本教程对您有所帮助。

基础教程