C言語でポインタを使って文字列が回文かどうかを判定する方法

はじめに

文字列 s が与えられたとき、その文字列が回文（パリンドローム）であるかどうかを判定することを考えます。ここでは、C言語のポインタを使ってこの問題を解いていきます。

例えば、入力が s = "racecar" の場合、出力は True（1） になります。「racecar」は前から読んでも後ろから読んでも同じ文字列だからです。

解法のアプローチ

この問題は、2つのポインタを文字列の両端に置き、中央に向かって互いに近づけていくことで効率的に判定できます。手順は以下の通りです。

• 文字列の長さを取得する
• ポインタ forward を文字列の先頭文字に向ける
• ポインタ reverse を文字列の末尾文字に向ける
• reverse の位置が forward の位置以上である間、以下を繰り返す
  • 両ポインタが指す文字が一致していれば、forward を1つ進め、reverse を1つ戻す
  • 一致しなければループを抜ける
• 最終的に forward の位置が reverse の位置以上であれば回文として True を返す
• そうでなければ False を返す

実装例

それでは、実際のコードを見て理解を深めましょう。

#include <stdio.h>
#include <string.h>

int solve(char *string){
    int length;
    char *forward, *reverse;

    length = strlen(string);
    forward = string;
    reverse = forward + length - 1;

    for (forward = string; reverse >= forward;) {
        if (*reverse == *forward) {
            reverse--;
            forward++;
        } else
            break;
    }

    if (forward > reverse)
        return 1;
    else
        return 0;
}

int main(){
    char string[] = "racecar";
    printf("%d", solve(string));
}

入力

"racecar"

出力

1

コードの解説

solve 関数では、まず strlen で文字列の長さを求め、先頭へのポインタ forward と末尾へのポインタ reverse を設定します。次に for ループの中で、*forward と *reverse（各ポインタが指す文字）を比較し、一致すれば両ポインタを中央方向へ移動させます。途中で不一致が見つかれば即座にループを抜けます。

ループ終了後、forward > reverse が成立している場合はすべての文字が一致したことを意味するため、回文として 1（True） を返します。

このアルゴリズムの計算量は O(n/2)、つまり O(n) であり、追加の配列など余分なメモリも不要なため、非常に効率的な方法と言えます。