C++で、逆順の文字列が同じ配列内に存在する最初の文字列を見つける方法

この問題では、サイズNの文字列配列 str[] が与えられます。求められるのは、「配列内にその逆順の文字列も存在するような、最初の文字列を見つけるプログラムを作成すること」です。

問題の例

具体例を使って問題を確認してみましょう。

入力: str[] = ["python", "program", "C#", "language", "#C"]
出力: C#

この例では、「C#」を逆順にした「#C」が同じ配列内に存在するため、「C#」が答えとなります。

解法アプローチ1：全探索（総当たり法）

最もシンプルな解き方は、文字列配列の各要素を順番に走査し、残りの要素の中にその文字列の逆順が存在するかどうかをチェックする方法です。逆順の文字列が見つかった場合はその文字列を返し、配列全体を走査しても該当する文字列が見つからなかった場合は -1 を返します。

実装例

この解法の動作を示すプログラムは以下の通りです。

#include<iostream>
#include<string.h>
using namespace std;
bool checkStringRev(string s1, string s2)
{
   if (s1.length() != s2.length())
      return false;
   int len = s1.length();
   for (int i = 0; i < len; i++)
      if (s1[i] != s2[len - i - 1])
          return false;
   return true;
}
string checkRevStringArr(string strArr[], int n){
   for (int i = 0; i < n - 1; i++)
      for (int j = i + 1; j < n; j++)
         if (checkStringRev(strArr[i], strArr[j]))
             return strArr[i];
   return "-1";
}
int main(){
   string strArr[] = { "python", "program", "C#", "language", "#C" };
   int n = sizeof(strArr)/sizeof(strArr[0]);
   cout<<"逆順の文字列が配列内に存在する最初の文字列は " <<checkRevStringArr(strArr, n);
}

出力

逆順の文字列が配列内に存在する最初の文字列は C#

この方法は実装が簡単ですが、二重ループを使用するため計算量はO(N² × L)（Lは文字列の長さ）となり、配列サイズが大きくなると非効率になります。

解法アプローチ2：ハッシュマップを使った線形時間での解決

より効率的な方法として、ハッシュマップを使えば線形時間（単一の走査）で問題を解くことができます。手順は以下の通りです。

• 配列を先頭から順に走査し、各文字列をハッシュマップに格納していきます。
• 各文字列について、その逆順の文字列がすでにハッシュマップに存在するかを確認します。
• 存在すれば、その逆順の文字列（ハッシュマップ側の文字列）が答えとなります。
• 配列全体を走査しても該当する文字列がなければ、-1を返します。

実装例

#include<bits/stdc++.h>
using namespace std;
string checkRevStringArr(string strArr[], int length){
   map<string,bool> stringHashMap;
   for(int i = 0; i < length; i++) {
      string str = strArr[i];
      reverse(str.begin(),str.end());
      if (stringHashMap.find(str) != stringHashMap.end() and stringHashMap[str])
         return str;
      else
         stringHashMap[strArr[i]] = true;
   }
   return "-1";
}
int main(){
   string strArr[] = { "python", "program", "C#", "language", "#C" };
   int n = sizeof(strArr)/sizeof(strArr[0]);
   cout<<"逆順の文字列が配列内に存在する最初の文字列は "<<checkRevStringArr(strArr, n);
}

出力

逆順の文字列が配列内に存在する最初の文字列は C#

まとめ

小規模なデータであれば全探索でも十分ですが、パフォーマンスが重要な場面ではハッシュマップを活用した線形時間のアプローチが推奨されます。状況に応じて最適な手法を選択しましょう。