【C++】2つの文字列を分割して回文が作れるか判定するプログラムの書き方

回文とは

反転しても元の並びと変わらない文字列のことを「回文」と呼びます。

本記事では、同じ長さを持つ2つの文字列「a」と「b」が与えられたとき、それぞれを任意のインデックスで分割し、一方の接頭辞(前方部分)と他方の接尾辞(後方部分)を組み合わせて回文が作れるかどうかを判定する方法を解説します。

例として、長さ4の2つの文字列「a」と「b」をインデックス3で分割すると、次のようになります。

aaa | b と bbb | a

このとき、以下のいずれかが成立すれば回文と判断できます。

• aaa(1つ目の文字列の接頭辞)+ a(2つ目の文字列の接尾辞)が回文である
• b(1つ目の文字列の接尾辞)+ bbb(2つ目の文字列の接頭辞)が回文である

入力例1

a = "abcdef"
b = "fedcba"

出力:

True

説明: 文字列「a」と「b」をインデックス2で分割すると、「abc | def」と「fed | cba」になります。このとき、abc(1つ目の文字列の接頭辞)+ cba(2つ目の文字列の接尾辞)が回文となるため、「True」を返します。

入力例2

a = "eatable"
b = "tableau"

出力:

False

説明: どの位置で分割しても回文を作ることができないため、「False」を返します。

この問題へのアプローチ

本問題は「two-pointer(双方向ポインタ)」手法を用いることで効率的に解くことができます。まず、lowとhighという2つのポインタを用意し、lowは先頭(0)、highは文字列の末尾の文字を指すように初期化します。

両文字列の長さは等しいため、どちらかの長さが2文字未満であればTrueを返します。それ以外の場合は、ポインタを動かしながら文字列全体を走査し、条件を満たすかどうかを再帰的に確認します。最終的に条件を満たせばTrueを、満たさなければFalseを返します。

アルゴリズムの手順

• 2つの文字列「a」と「b」を受け取ります。
• ブール関数 checkPalindromic(string a, string b) は、2つの文字列を入力パラメータとして受け取り、結果に応じてTrueまたはFalseを返します。
• 2つのポインタ low と high を初期化します(low = 0、high = 文字列「b」の長さ)。
• 文字列を走査し、両者の対応する文字が一致しているかどうかを確認します。
• ブール関数 Split(string a, string b) は、2つの文字列を受け取り、回文が作れればTrue、そうでなければFalseを返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string a, int low, int high) {
    while (low < high) {
        if (a[low] != a[high])
            return false;
        low++;
        high--;
    }
    return true;
}
bool Split(string a, string b) {
    int low = 0;
    int high = b.size() - 1;
    while (low < high and a[low] == b[high]) {
        low++;
        high--;
    }
    return isPalindrome(a, low, high) || isPalindrome(b, low, high);
}
bool checkPalindromic(string a, string b) {
    if (a.size() < 2)
        return true;
    return Split(a, b) || Split(b, a);
}
int main() {
    string a = "abcpqr";
    string b = "mnocba";
    if (checkPalindromic(a, b)) {
        cout << "True" << endl;
    } else {
        cout << "False" << endl;
    }
    return 0;
}

上記のコードを実行すると、次の出力が得られます。

出力

True

説明: 与えられた文字列「abcpqr」と「mnocba」をインデックス2で分割すると、

a(接頭辞)= abc および b(接尾辞)= cba
a(接尾辞)= pqr および b(接頭辞)= mno

となり、a(接頭辞)+ b(接尾辞)を連結した「abccba」は回文になっていることが確認できます。したがって、出力はTrueとなります。