Java 中的回文

原文：https://www.studytonight.com/java-examples/palindrome-in-java

如果一个字符串从头到尾读起来都一样，那么它就被称为回文。从字符串的开头或结尾读取时，所有字符都以相同的顺序出现。回文的例子有“Bob”、“Naman”、“Racecar”、“dide”等。

在本教程中，我们将学习如何检查一个字符串是否是回文。

解决方案 1:使用两个指针

我们可以使用两个指针来检查一个字符串是否是回文。一个指针将从字符串的开头开始，并向前移动。第二个指针从字符串的末尾开始，并向后移动。在每次迭代中，如果出现在两个指针上的字符相同，那么我们将移动指针。否则，我们将返回 false。我们还会将输入字符串转换为小写。

public class Demo
{
    public static boolean isPalindrome(String str)
    {
        int startIdx = 0;
        int endIdx = str.length() - 1;        
        while(startIdx < endIdx)
        {
            char start = str.charAt(startIdx);
            char end = str.charAt(endIdx);
            if(Character.toLowerCase(start) != Character.toLowerCase(end))
                return false;
            startIdx += 1;
            endIdx -= 1;
        }
        return true;
    }    
    public static void main(String[] args)
    {
        System.out.println("racecar is palindrome: " + isPalindrome("racecar"));
        System.out.println("RaCeCar is palindrome: " + isPalindrome("RaCeCar"));
        System.out.println("naman is palindrome: " + isPalindrome("naman"));
        System.out.println("Deed is palindrome: " + isPalindrome("Deed"));
        System.out.println("Java is palindrome: " + isPalindrome("Java"));
    }
}

racecar 是回文:真 RaCeCar 是回文:真 纳曼是回文:真 契是回文:真 Java 是回文:假

使用递归方法查找回文

我们可以递归地实现上面的代码。递归可以有两种基本情况:

• 如果字符串包含单个字符，则返回 true。

• 如果开始指针和结束指针字符在任何时候都不相等，则返回 false。

递归解决方案的完整代码如下所示。

public class Demo
{
    public static boolean isPalindrome(String str)
    {
        String lowercaseStr = str.toLowerCase();

        return isPalindromeRecursive(lowercaseStr, 0, lowercaseStr.length() - 1);
    }

    public static boolean isPalindromeRecursive(String str, int startIdx, int endIdx)
    {
        if(startIdx == endIdx)//Single character string
            return true;

        if(str.charAt(startIdx) != str.charAt(endIdx))
            return false;

        if(startIdx < endIdx + 1)
            return isPalindromeRecursive(str, startIdx + 1, endIdx - 1);

        return true;
    }

    public static void main(String[] args)
    {
        System.out.println("racecar is a palindrome: " + isPalindrome("racecar"));
        System.out.println("RaCeCar is a palindrome: " + isPalindrome("RaCeCar"));
        System.out.println("naman is a palindrome: " + isPalindrome("naman"));
        System.out.println("Deed is a palindrome: " + isPalindrome("Deed"));
        System.out.println("Java is a palindrome: " + isPalindrome("Java"));
    }
}

racecar 是回文:真 RaCeCar 是回文:真 纳曼是回文:真 契是回文:真 Java 是回文:假

解决方案 2:反转字符串

我们可以使用 StringBuilder 或 StringBuffer 类来反转输入字符串。如果反串和原串一样，那么就是回文。

我们可以通过以相反的方向(从右到左)遍历字符串来手动反转字符串。

public static boolean isPalindrome(String str)
{
    String lowercaseStr = str.toLowerCase();
    StringBuilder reverseSB = new StringBuilder();
    //Reversing the string
    for(int i = lowercaseStr.length() - 1; i >= 0; i--)
        reverseSB.append(lowercaseStr.charAt(i));

    String reversedStr = reverseSB.toString();
    return lowercaseStr.equals(reversedStr);
}

或者我们可以使用 StringBuilder 类的 reverse() 方法。

public static boolean isPalindrome(String str)
{
    String lowercaseStr = str.toLowerCase();

    StringBuilder sb = new StringBuilder(lowercaseStr);
    StringBuilder reversedSB = sb.reverse();//Reversing the string

    String reversedStr = reversedSB.toString();
    return lowercaseStr.equals(reversedStr);
}

让我们在一些字符串上测试这种方法，并查看输出。

public static void main(String[] args)
{
    System.out.println("racecar is a palindrome: " + isPalindrome("racecar"));
    System.out.println("RaCeCar is a palindrome: " + isPalindrome("RaCeCar"));
    System.out.println("naman is a palindrome: " + isPalindrome("naman"));
    System.out.println("Deed is a palindrome: " + isPalindrome("Deed"));
    System.out.println("Java is a palindrome: " + isPalindrome("Java"));
}

racecar 是回文:真 RaCeCar 是回文:真 纳曼是回文:真 契是回文:真 Java 是回文:假

解决方案 3:使用 Java 8 流

流 API 也可以用来检查回文字符串。我们将使用 IntStream 类来遍历字符串。接下来，我们将使用 noneMatch() 方法和一个谓词。

import java.util.stream.IntStream;

public class Demo
{
    public static boolean isPalindrome(String str)
    {
        String lowercaseStr = str.toLowerCase();
        return IntStream.range(0, lowercaseStr.length() / 2)
                       .noneMatch(i -> lowercaseStr.charAt(i) != lowercaseStr.charAt(lowercaseStr.length() - i - 1));
    }

    public static void main(String[] args)
    {
        System.out.println("racecar is a palindrome: " + isPalindrome("racecar"));
        System.out.println("RaCeCar is a palindrome: " + isPalindrome("RaCeCar"));
        System.out.println("naman is a palindrome: " + isPalindrome("naman"));
        System.out.println("Deed is a palindrome: " + isPalindrome("Deed"));
        System.out.println("Java is a palindrome: " + isPalindrome("Java"));
    }
}

racecar 是回文:真 RaCeCar 是回文:真 纳曼是回文:真 契是回文:真 Java 是回文:假

摘要

在本教程中，我们讨论了检查字符串是否是回文的不同方法。我们可以使用简单的两点方法。该方法可以迭代或递归实现。我们还可以反转字符串，检查反转后的字符串是否与原始字符串相同。也可以使用 Java 8 流。

反转字符串将总是给出 0(n)的时间复杂度。另一方面，双指针方法性能更好，并且返回 O(1)的最佳时间复杂度。当字符串两端的字符不匹配时，出现双指针方法的最佳情况。双指针方法最差的时间复杂度是 O(n)。