检查字符串是否为回文

回文是指正着读和反着读都是一样的序列，比如 "level" 和 "racecar" 就是回文。在这篇文章中，我们将探讨如何检查一个字符串是否为回文。

方法一：使用双指针

使用双指针是检查字符串是否为回文最直接的方法之一。我们可以使用两个指针，一个指向字符串的开头，一个指向字符串的结尾，然后比较两个指针所指向的字符是否相等。如果两个字符相等，则继续向中间移动指针；如果不相等，则说明该字符串不是回文，可以直接返回 false。

下面是使用双指针实现的代码示例：

public static boolean isPalindrome(String str) {

    int i = 0;

    int j = str.length() - 1;

    while (i < j) {

        if (str.charAt(i) != str.charAt(j)) {

            return false;

        }

        i++;

        j--;

    }

    return true;

}

在以上代码中，我们使用了两个变量 i 和 j 来分别指向字符串的开头和结尾。然后我们使用 while 循环，不断地比较字符串的头尾字符是否相等，直到两个指针相遇或者不相等为止。

这种方法的时间复杂度是 O(n)，其中 n 是字符串的长度。

但是需要注意的是，这种方法只能处理纯字符串，不能处理字符串中的非字母数字字符。如果字符串中包含非字母数字字符，需要先将其过滤掉再进行比较。

方法二：使用栈

另一个检查字符串是否为回文的方法是使用栈。我们可以将字符串的字符一个一个入栈，然后再出栈和原字符串比较。

下面是使用栈实现的代码示例：

public static boolean isPalindrome(String str) {

    Stack<Character> stack = new Stack<>();

    for (int i = 0; i < str.length(); i++) {

        stack.push(str.charAt(i));

    }

    for (int i = 0; i < str.length(); i++) {

        if (str.charAt(i) != stack.pop()) {

            return false;

        }

    }

    return true;

}

在以上代码中，我们使用了一个栈来存储字符串的字符。首先，我们使用 for 循环将字符串的字符依次入栈。然后，我们再使用 for 循环将栈中的字符依次出栈与原字符串比较。

这种方法的时间复杂度也是 O(n)，其中 n 是字符串的长度。但是需要注意的是，这种方法需要额外的空间来存储栈，如果字符串很长，可能会出现栈溢出的情况。

方法三：使用递归

最后一个检查字符串是否为回文的方法是使用递归。我们可以使用递归来比较字符串的头尾字符是否相等。

下面是使用递归实现的代码示例：

public static boolean isPalindrome(String str) {

    if (str.length() <= 1) {

        return true;

    }

    if (str.charAt(0) != str.charAt(str.length() - 1)) {

        return false;

    }

    return isPalindrome(str.substring(1, str.length() - 1));

}

在以上代码中，我们使用了递归来比较字符串的头尾字符是否相等。如果字符串的长度小于等于 1，则说明字符串是回文；如果头尾字符不相等，则说明字符串不是回文。否则，我们可以将字符串截取掉头尾字符，再使用递归判断剩余字符串是否为回文。

这种方法的时间复杂度是 O(n)，其中 n 是字符串的长度。但是需要注意的是，这种方法可能会出现栈溢出的情况，因为递归调用会使用到栈空间。

总结

以上介绍了三种检查字符串是否为回文的方法：双指针、栈和递归。这三种方法时间复杂度都是 O(n)，其中 n 是字符串的长度。其中，双指针方法是最常用的方法，因为其代码简单、可读性好，并且空间复杂度很小。但是需要注意的是，双指针方法只能处理纯字符串，不能处理字符串中的非字母数字字符。如果字符串中包含非字母数字字符，需要先将其过滤掉再进行比较。