检查字符串是否为回文字符串

Question

一个回文是指一个单词、短语、数字或其他单元的序列，在任一方向上读取时都是相同的。

要检查一个单词是否为回文，我会获取该单词的字符数组并比较其字符。我测试过了，似乎可以正常工作。但是我想知道它是否正确，或者是否有什么需要改进的地方。

以下是我的代码：

public class Aufg1 {
    public static void main(String[] args) {
        String wort = "reliefpfpfeiller";
        char[] warray = wort.toCharArray(); 
        System.out.println(istPalindrom(warray));       
    }

    public static boolean istPalindrom(char[] wort){
        boolean palindrom = false;
        if(wort.length%2 == 0){
            for(int i = 0; i < wort.length/2-1; i++){
                if(wort[i] != wort[wort.length-i-1]){
                    return false;
                }else{
                    palindrom = true;
                }
            }
        }else{
            for(int i = 0; i < (wort.length-1)/2-1; i++){
                if(wort[i] != wort[wort.length-i-1]){
                    return false;
                }else{
                    palindrom = true;
                }
            }
        }
        return palindrom;
    }
}

- DarkLeafyGreen

---

不确定这是否是有意的，但您例子中的字符串 - reliefpfpfeiller - 不是回文。 - barrowc

Answer 1

为什么不这样做：

public static boolean istPalindrom(char[] word){
    int i1 = 0;
    int i2 = word.length - 1;
    while (i2 > i1) {
        if (word[i1] != word[i2]) {
            return false;
        }
        ++i1;
        --i2;
    }
    return true;
}

例子：

输入为 "andna"。
i1 将是 0 而 i2 将是 4。

第一次循环迭代我们将比较 word[0] 和 word[4]。它们相等，所以我们增加 i1（现在它是1）并减小 i2（现在它是3）。
然后我们比较 n。它们相等，所以我们增加 i1（现在它是2）并减小 i2（现在它是2）。
现在 i1 和 i2 相等（它们都是2），因此 while 循环的条件不再为真，所以循环终止并返回 true。

- dcp

---

我们可以使用后增量（i1++，i2--）代替前增量（++i1和--i2），我认为结果是相同的！ - user0946076422

@user0946076422 是的，我也有同感。如果 OP 有不同的解释会很好。 - Vijay Tholpadi

这只是一种编码偏好，与其他任何事情无关。在这个特定的例子中，后增量可以完成相同的结果，但我总是使用前增量，除非有特别的原因不使用。 - dcp

Answer 2

你可以通过将字符串与其反转后的形式进行比较来检查它是否是回文：

public static boolean isPalindrome(String str) {
    return str.equals(new StringBuilder(str).reverse().toString());
}

或者是针对Java 1.5以前的版本，

public static boolean isPalindrome(String str) {
    return str.equals(new StringBuffer().append(str).reverse().toString());
}

编辑: @FernandoPelliccioni 提供了一份非常详尽的分析报告，对于这个解决方案的时间和空间效率（或缺乏效率）进行了分析。如果你对这个问题以及其他可能的解决方案的计算复杂度感兴趣，请阅读它！

- Greg

---

将您的算法复杂度与其他算法进行比较。 - Fernando Pelliccioni

@FernandoPelliccioni，我认为这个解决方案的复杂度和其他解决方案是一样的，不是吗？ - aioobe

@Fernando，就我所知，所有答案的复杂度都是线性的。因此，无法确定哪个解决方案最有效。您可以运行基准测试，但它们将特定于特定的JVM和JRE。祝您在博客文章中好运。期待阅读。 - aioobe

太贵了，一个简单的循环可以更高效地完成更好的工作。 - Martin A

使用内置的reverse()函数是作弊 :) - ses

Answer 3

一个简洁的版本，不需要（低效地）初始化一堆对象：

boolean isPalindrome(String str) {    
    int n = str.length();
    for( int i = 0; i < n/2; i++ )
        if (str.charAt(i) != str.charAt(n-i-1)) return false;
    return true;    
}

- Andrew Mao

Answer 4

或者，递归。

对于任何想要寻找更短的递归解决方案来检查给定字符串是否为回文的人：

private boolean isPalindrome(String s) {
    int length = s.length();

    if (length < 2) // If the string only has 1 char or is empty
        return true;
    else {
        // Check opposite ends of the string for equality
        if (s.charAt(0) != s.charAt(length - 1))
            return false;
        // Function call for string with the two ends snipped off
        else
            return isPalindrome(s.substring(1, length - 1));
    }
}

---

或者更加简洁，如果您喜欢：

---

private boolean isPalindrome(String s) {
    int length = s.length();
    if (length < 2) return true;
    return s.charAt(0) != s.charAt(length - 1) ? false :
            isPalindrome(s.substring(1, length - 1));
}

- Keith OYS

---

简化的版本为：return s.charAt(0) == s.charAt(s.length() - 1) && isPalindrome(s.substring(1, s.length() - 1));该代码判断一个字符串是否为回文字符串，即字符串从左往右和从右往左读取都是一样的。 - vault

Answer 5

Go、Java：

public boolean isPalindrome (String word) {
    String myWord = word.replaceAll("\\s+","");
    String reverse = new StringBuffer(myWord).reverse().toString();
    return reverse.equalsIgnoreCase(myWord);
}

isPalindrome("Never Odd or Even"); // True
isPalindrome("Never Odd or Even1"); // False

- Francisco Gutiérrez

Answer 6

public class Palindromes {
    public static void main(String[] args) {
         String word = "reliefpfpfeiller";
         char[] warray = word.toCharArray(); 
         System.out.println(isPalindrome(warray));       
    }

    public static boolean isPalindrome(char[] word){
        if(word.length%2 == 0){
            for(int i = 0; i < word.length/2-1; i++){
                if(word[i] != word[word.length-i-1]){
                    return false;
                }
            }
        }else{
            for(int i = 0; i < (word.length-1)/2-1; i++){
                if(word[i] != word[word.length-i-1]){
                    return false;
                }
            }
        }
        return true;
    }
}

- Casey

---

你尝试过用 "cbb" 运行 isPalindrome() 吗？ - kenshinji

Answer 7

另外还有一个不同外观的解决方案：

public static boolean isPalindrome(String s) {

        for (int i=0 , j=s.length()-1 ; i<j ; i++ , j-- ) {

            if ( s.charAt(i) != s.charAt(j) ) {
                return false;
            }
        }

        return true;
    }

- Mona Jalal

Answer 8

这里是一个完整的Java 8 流式处理解决方案。一个IntStream提供了所有字符串一半长度的索引，然后从开头和结尾进行比较。

public static void main(String[] args) {
    for (String testStr : Arrays.asList("testset", "none", "andna", "haah", "habh", "haaah")) {
        System.out.println("testing " + testStr + " is palindrome=" + isPalindrome(testStr));
    }
}

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

输出结果为：

testing testset is palindrome=true
testing none is palindrome=false
testing andna is palindrome=true
testing haah is palindrome=true
testing habh is palindrome=false
testing haaah is palindrome=true

- wumpz

---

为什么不能使用 allMatch(i -> str.charAt(i) == str.charAt(str.length() - i - 1)) 进行匹配？ - gil.fernandes

Answer 9

我为一个被标记为重复的问题工作，提供了一个解决方案。这里也可以分享一下...

此问题要求使用单行代码解决，但我认为这更像一个文学回文 - 因此空格、标点符号和大小写可能会影响结果。

下面是一个丑陋的解决方案以及一个小型测试类：

public class Palindrome {
   public static boolean isPalendrome(String arg) {
         return arg.replaceAll("[^A-Za-z]", "").equalsIgnoreCase(new StringBuilder(arg).reverse().toString().replaceAll("[^A-Za-z]", ""));
   }
   public static void main(String[] args) {
      System.out.println(isPalendrome("hiya"));
      System.out.println(isPalendrome("star buttons not tub rats"));
      System.out.println(isPalendrome("stab nail at ill Italian bats!"));
      return;
   }
}

很抱歉这有点讨厌，但其他问题指定了一个一行代码。

- Marc

Answer 10

检查字符串的前一半与后一半是否回文，此情况假定移除任何空格。

public int isPalindrome(String a) {
        //Remove all spaces and non alpha characters
        String ab = a.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
        //System.out.println(ab);

        for (int i=0; i<ab.length()/2; i++) {
            if(ab.charAt(i) != ab.charAt((ab.length()-1)-i)) {
                return 0;
            }
        }   
        return 1;
    }

- Abhilash Muthuraj