C++で文字列配列から回文ペアを見つける方法【総当たり法とトライ木による最適化】

「Madam」や「racecar」のように、前から読んでも後ろから読んでも同じになる言葉を「回文（パリンドローム）」と呼びます。

文字列のリストが与えられたとき、その中から任意の2つの文字列を選んで連結した結果が回文になるペアが存在するかどうかを判定するC++プログラムを書いてみましょう。該当するペアが存在すれば「Yes」を、存在しなければ「No」を出力します。

このチュートリアルでは、入力として文字列の配列を受け取り、判定結果を文字列として出力します。以下に具体例を示します。

入出力例

入力

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

出力

Yes

この例では、「flat」と「ptalf」のペアを連結すると回文「flatptalf」が形成されます。

入力

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

出力

Yes

こちらの例では、「na」と「man」のペアを連結すると回文「naman」が形成されます。

解法アプローチ①：総当たり（ブルートフォース）法

最もシンプルな方法は、配列内の各文字列について、他のすべての文字列との組み合わせを順番にチェックし、連結した結果が回文になるかどうかを調べることです。回文になるペアが1つでも見つかればtrueを返し、すべての組み合わせを調べても見つからなければfalseを返します。

• 時間計算量：O(N²)
• 空間計算量：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を返す

• 時間計算量：O(Nk²)
• 空間計算量：O(N)

ここで、Nはリスト内の単語数、kは回文判定の対象となる最大文字列長を表します。

実装例

#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

まとめ

本チュートリアルでは、文字列配列の中から回文ペアを見つける2つのアプローチ（総当たり法とトライ木による最適化手法）を学びました。ここで紹介したロジックは、JavaやPythonなど他のプログラミング言語にも容易に応用できます。総当たり法はすべての要素を順に調べる基本的な手法である一方、トライ木を用いた手法はほぼ線形時間で答えを導き出せるため、大量のデータを扱う場面で威力を発揮します。ぜひ実際のコードを動かしながら、両者の違いを体感してみてください。