C言語での回文文字列アルゴリズムの実装方法

2年 ago
優斗, 朝陽
1 minute

回文判定アルゴリズムの一般的な手法は、文字列の最初と最後の文字を比較して回文であるかどうかを判定します。具体的には、以下の手順で実現します。

  1. 文字列の先頭の文字を指すポインタと、文字列の末尾の文字を指すポインタの2つを定義します。
  2. 順番に先頭と末尾の文字を比較し、同じであれば次の文字を比較し、違う場合は回文文字列ではありません。
  3. ポインタが交差または重なると、すべての文字の比較は完了しており、すべての文字が一致すると回文です。
  4. ループ終了時点でポインタが交差または重なっていない場合、それは特有の文字が存在し、回文でないことを表します。

以下にC言語による簡単な実装例を示す。

#include <stdio.h>
#include <stdbool.h> // 引入bool类型

bool isPalindrome(char *str) {
    int left = 0;            // 左指针
    int right = strlen(str) - 1; // 右指针

    while (left < right) {
        if (str[left] != str[right]) {
            return false; // 不相等，不是回文字符串
        }
        left++;
        right--;
    }

    return true; // 通过循环，指针交叉或重合，是回文字符串
}

int main() {
    char str[100];
    printf("请输入一个字符串：");
    scanf("%s", str);

    if (isPalindrome(str)) {
        printf("是回文字符串\n");
    } else {
        printf("不是回文字符串\n");
    }
    return 0;
}

入力された文字列に空白やその他の特殊文字が含まれている場合、それらの特殊文字を除去するために事前に処理する必要があります。このアルゴリズムの時間計算量は O(n) になり、n は文字列の長さです。

bannerAds