C++で再帰関数を使って文字列が回文かどうかを判定する方法

入力として文字列 Str が与えられます。目的は、再帰関数を使用して、入力された文字列が回文（パリンドローム）であるかどうかを判定することです。

回文とは、前から読んでも後ろから読んでも同じ言葉になる文字列のことです。長さが0の文字列も回文とみなされます。回文を文字単位で逆順に並べ替えても、元の文字列とまったく同じ文字列になります。

回文の例としては、madam、abcba、malayalam などが挙げられます。

実行例

入力 − Str = "malayalam"

出力 − 入力文字列は回文です。

説明 −

Str[0〜8] = malayalam

逆順にした Str[8〜0] = malayalam

両者の文字列は同一であるため、回文と判定されます。

入力 − Str = "tutorial"

出力 − 入力文字列は回文ではありません。

説明 −

Str[0〜7] = tutorial

逆順にした Str[7〜0] = lairotut

両者の文字列が異なるため、回文ではないと判定されます。

プログラムで使用するアプローチ

このアプローチでは、まず文字列が1文字のみで構成されているかどうかを確認します。1文字だけであれば、それは回文です。1文字でない場合は、残りの文字に対して再帰的に文字列全体を走査し、対応する位置の文字が一致しない時点で再帰を中断します。

• 入力文字列 Str[] を受け取り、その長さを計算します。
• 長さが0の場合は、result = 1 を設定します。
• それ以外の場合は、result = checkPalindrome(Str, 0, length - 1) を設定します。ここで 0 は先頭のインデックス、length - 1 は末尾のインデックスを表します。
• 関数 checkPalindrome(char str[], int first, int last) は、文字列内の対応する文字と一致しない文字が存在した場合に 0 を返します。
• インデックス first と last が同じ場合、文字列は1文字しか持たないため、1 を返します。
• そうでない場合は、first++ および last-- として両端の文字を除外し、残りの文字について checkPalindrome(str, first, last) を再帰的に呼び出します。
• すべての再帰呼び出しが完了した時点で、最終的な結果が得られます。
• 結果が 1 であれば、入力文字列は回文です。
• それ以外の場合、入力文字列は回文ではありません。
• main 関数内で結果を出力します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int checkPalindrome(char str[], int first, int last){
    if (first < last + 1){
        first++;
        last--;
        return checkPalindrome(str, first, last);
    }

    if (first == last){
        return 1;
    }
    if (str[first] != str[last]){
        return 0;
    }
    return 1;
}
// ドライバーコード
int main(){
    char Str[] = "madam";
    int result;
    int length = strlen(Str);
    if (length == 0){
        result = 1;
    }

    else{
        result = checkPalindrome(Str, 0, length - 1);
    }
    if (result == 1){
        cout << "Input string is palindrome.";
    }
    else{
        cout << "Input string is not a palindrome.";
    }
    return 0;
}

出力

上記のコードを実行すると、次のような出力が生成されます。

Input string is palindrome.