给定一个字符串，如何判断这个字符串是否是回文串？ 请实现两种算法，并给出算法的时间复杂度分析。

判断回文串的算法有多种，我这里介绍两种比较常见的算法。

方法一：双指针法

我们可以用双指针从两端开始遍历字符串，判断对应字符是否相等，如果不相等，则不是回文串。具体实现如下：

def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

时间复杂度分析：双指针法只需要遍历一次字符串，时间复杂度为 $O(n)$。

方法二：翻转法

我们可以将字符串翻转过来，然后和原字符串进行比较，如果相等，则是回文串。具体实现如下：

def is_palindrome(s):
    return s == s[::-1]

时间复杂度分析：字符串翻转需要 $O(n)$ 的时间，比较两个字符串需要 $O(n)$ 的时间，总时间复杂度为 $O(n)$。

两种方法时间复杂度都是 $O(n)$，但是双指针法可能会更快一些，因为字符串翻转需要额外的内存空间。

相关问题

给定一个字符串，如何判断这个字符串是否是回文串？ 请用c语言或c++实现两种算法，并给出算法的时间复杂度分析。

判断回文串的两种算法如下：

算法1：双指针法

思路：使用两个指针从字符串的左右两端同时向中间扫描，如果左右两端的字符不相同，返回false，否则继续扫描，直到两个指针相遇，返回true。

时间复杂度：O(n)，其中n为字符串的长度。

代码如下：

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

int isPalindrome(char* s) {
    int len = strlen(s);
    int left = 0, right = len - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            return 0; // 不是回文串
        }
        left++;
        right--;
    }
    return 1; // 是回文串
}

int main() {
    char s[] = "abcdcba";
    if (isPalindrome(s)) {
        printf("%s is a palindrome\n", s);
    } else {
        printf("%s is not a palindrome\n", s);
    }
    return 0;
}

算法2：递归法

思路：判断字符串的第一个字符和最后一个字符是否相同，如果相同，则递归判断剩余子串是否为回文串，否则返回false。

时间复杂度：O(n)，其中n为字符串的长度。但是由于存在递归调用，所以空间复杂度可能比较高。

代码如下：

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

int isPalindrome(char* s, int left, int right) {
    if (left >= right) {
        return 1; // 是回文串
    }
    if (s[left] != s[right]) {
        return 0; // 不是回文串
    }
    return isPalindrome(s, left + 1, right - 1);
}

int main() {
    char s[] = "abcdcba";
    if (isPalindrome(s, 0, strlen(s) - 1)) {
        printf("%s is a palindrome\n", s);
    } else {
        printf("%s is not a palindrome\n", s);
    }
    return 0;
}

设计一个算法判断给定的字符串是否为回文?

可以使用双指针法，从字符串的两端开始向中间扫描，比较对应位置的字符是否相同。具体步骤如下：

1. 定义两个指针 i 和 j，分别指向字符串的首尾字符。
2. 循环比较字符串中 i 和 j 指向的字符是否相同，直到 i >= j。
3. 如果每一次比较的字符都相同，则该字符串是回文，否则不是回文。

代码实现如下：

def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

测试代码：

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))    # False