C ++で単語（または文字列）の配列で回文ペアを作成する

「マダム」または「レースカー」は、回文と呼ばれる、前方と同じ後方を読む2つの単語です。

文字列のコレクションまたはリストが与えられた場合、C ++コードを記述して、リスト内の任意の2つの文字列を結合して回文を形成できるかどうかを確認する必要があります。指定されたリストにそのような文字列のペアが存在する場合は、「はい」を出力する必要があります。それ以外の場合は、「いいえ」を出力する必要があります。

このチュートリアルでは、入力は文字列の配列になり、出力はそれに応じて文字列値になります。たとえば、

入力

list[] = {"flat", "tea", "chair", "ptalf", "tea"}

出力

Yes

回文文字列「flatptalf」を形成する「flat」と「ptalf」のペアがあります。

入力

list[] = {"raman", "ram", "na", "ar", "man"}

出力

Yes

回文文字列「naman」を形成する「na」と「man」のペアがあります。

解決策を見つけるためのアプローチ

ブルートフォースアプローチ

配列内の各文字列について、他のすべての文字列が他の文字列と回文を形成しているかどうかを確認します。そのようなペアが見つかった場合は、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

効率的または最適化されたアプローチ

この問題を解決するために、トライデータ構造を使用できます。

まず、空のトライを作成する必要があります。配列内の文字列ごとに、現在の単語の逆を挿入し、それが回文であるインデックスまで保存する必要があります。次に、配列を再度トラバースする必要があり、文字列ごとに、次のことを行う必要があります-

• 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

結論

このチュートリアルでは、2つのアプローチ（ブルートフォースと最適化）を使用して、配列内の回文ペアを見つける方法を学習しました。このコードは、Java、Python、およびその他の言語で作成することもできます。最初のアプローチは、指定されたすべての要素をトラバースすることによって解決策を見つける基本的な方法です。対照的に、2番目のアプローチでは、トライデータ構造を使用するため、ほぼ線形の時間計算量で答えが得られます。このチュートリアルがお役に立てば幸いです。