递归函数：在Java中检查回文

Question

我有一个类，用于检查一个字符串是否是回文。我有两个问题。

1）这是检查回文的最有效方式吗？ 2）这可以通过递归实现吗？

public class Words {

    public static boolean isPalindrome(String word) {
    String pal = null;
    word = word.replace(" ", "");
    pal = new StringBuffer(word).reverse().toString();
    if (word.compareTo(pal) == 0) {
        return true;
    } else {
        return false;
    }

    }

}

有一个测试类来测试这个... 不确定是否需要，但如果有人想尝试一下以帮助我解决上述两个问题，这里就是它...

public class testWords {

    public static void main(String[] args) {
    if (Words.isPalindrome("a") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("cat") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("w o    w") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("   a  ") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("mom!") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }

    }

}

感谢您提前的任何帮助和输入 :)

- choloboy7

---

当判断一个短语是否为回文时，您可能想要更改您认为有效字符的定义。例如，“Madam, I'm Adam”就是一个回文。 - Andrew Morton

所以我应该尝试让我的程序忽略掉像“'”这样的字符。 - choloboy7

http://stackoverflow.com/questions/1579977/palindrome-recursion-program?rq=1 - Rozuur

首先，过滤掉所有非字母数字字符，然后检查它是否为回文。 - Andrew Morton

return (word.compareTo(pal) == 0) 可以节省 if 的使用。 - Andrew Morton

在测试代码中，您同样可以这样写：System.out.println("" + Words.isPalindrome("whatever")) -- 布尔值会自动转换为相应的字符串"true"或"false"。 - user10762593

Answer 1

为了递归实现“回文检查”，您必须比较第一个和最后一个字符是否相同。如果它们不相同，则该字符串绝对不是回文。如果它们相同，则该字符串可能是回文，您需要将第二个字符与倒数第二个字符进行比较，以此类推，直到在字符串中要检查的字符数量严格小于2。

递归算法应如下所示：

public static boolean isPalindrome(String word) {
  //Strip out non-alphanumeric characters from string
  String cleanWord = word.replaceAll("[^a-zA-Z0-9]","");
  //Check for palindrome quality recursively
  return checkPalindrome(cleanWord);
}
private static boolean checkPalindrome(String word) {
  if(word.length() < 2) { return true;  }
  char first  = word.charAt(0);
  char last   = word.charAt(word.length()-1);
  if(  first != last  ) { return false; }
  else { return checkPalindrome(word.substring(1,word.length()-1)); }
}

• 请注意，我的递归方法并不是最有效的方法，但易于理解

• Marimuthu Madasamy有一种更有效的递归方法，但更难理解

• Joe F列出了一个同样有效的迭代方法，
  这是最佳实现方法，因为它不会导致stack overflow错误

- recursion.ninja

---

+1 这看起来是正确的，您能否向 OP 解释一下为什么这样做有效？ - Benjamin Gruenbaum

我认为你的基本情况应该是 word.length() < 2。 - Ajay

糟糕，我以为我修复了那个问题，internalPalindromeCheck 应该是 checkPalindrome 方法。 - recursion.ninja

@choloboy7 word.replaceAll("[^a-zA-Z0-9]",""); 这个语句告诉Java获取字符串，查找所有非字母数字字符，并用空字符串替换它们。我认为令人困惑的部分是 "[^a-zA-Z0-9]"。这被称为正则表达式（RegEx），它们是一种强大而多功能的工具。在适当的时候学习它们绝对是值得的。 - recursion.ninja

@choloboy7 这个特定的正则表达式 [^a-zA-Z0-9] 表示匹配除了字母 a-zA-Z 或数字 0-9 以外的所有内容。 - recursion.ninja

Answer 2

这里有另一种使用数组的递归解决方案，相较于在递归调用中避免使用 substring 或 charAt 的字符串方法，可以带来一些性能优势。

private static boolean isPalindrome(final char[] chars, final int from,
        final int to) {
    if (from > to) return true;
    return chars[from] != chars[to] ? false 
                                    : isPalindrome(chars, from + 1, to - 1);
}

public static boolean isPalindrome(final String s) {
    return isPalindrome(s.toCharArray(), 0, s.length() - 1);
}

这个算法的思路是我们在数组中保持两个位置，一个在开头，另一个在结尾，并且我们不断地将这些位置向中心移动。

当这些位置重叠并通过时，我们完成了所有字符的比较，到目前为止所有字符都匹配；该字符串是回文的。

每次比较时，如果字符不匹配，则该字符串不是回文，否则将位置更靠近中心。

- Marimuthu Madasamy

---

你的解决方案很优雅，但我担心对于初学者来说它太晦涩难懂了。也许可以添加一些注释？ - recursion.ninja

当然，让我稍微扩展一下。 - Marimuthu Madasamy

Answer 3

实际上只需要检查到中间字符就足以确认它是回文，这意味着你可以将其简化为以下内容：

// Length of my string.
int length = myString.length();

// Loop over first half of string and match with opposite character.
for (int i = 0; i <= length / 2; i++) {
    // If we find one that doesn't match then return false.
    if (myString.charAt(i) != myString.charAt(length - 1 - i)) return false;
}

// They all match, so we have found a palindrome!
return true;

递归解决方案是完全可行的，但它不会给你带来任何性能优势（可能不像可读性那么好）。

- Joe F

---

我不明白。难道不需要检查单词的后半部分吗？如何仅通过检查到中间字符就能保证它是回文？ - choloboy7

@choloboy7 因为你已经检查了后半部分；当你检查第一个字符时，将其与最后一个进行比较，当你比较第二个字符时，将其与倒数第二个进行比较。当你到达中间时，所有字符都已经被比较过了。 - recursion.ninja

Answer 4

我的看法。看到不同的人解决问题的方式总是很好的。当然，这并不是最有效的算法，无论是在内存还是速度方面。

public static boolean isPalindrome(String s) {

    if (s.length() <= 1) { // got to the middle, no need for more checks
        return true;
    }

    char l = s.charAt(0); // first char
    char r = s.charAt(s.length() - 1); // last char

    if (l == r) { // same char? keep checking
        String sub = s.substring(1, s.length() - 1);
        return isPalindrome(sub);
    }

    return false;
}

- Hlodowig

Answer 5

这个能用递归实现吗？

可以
以下是示例：

public static boolean palindrome(String str)
{
    if (str.length()==1 || str.length == 0)
    return true;
    char c1 = str.charAt(0);
    char c2 = str.charAt(str.length() - 1);
    if (str.length() == 2)
    {
        if (c1 == c2)
        return true;
        else
        return false;
    }
    if (c1 == c2)
    return palindrome(str.substring(1,str.length() - 1));
    else
    return false;
}

- Vishal K

---

@awashburn：除了长度为0的单词，你能告诉我它在哪些单词上失败了吗？ - Vishal K

所以这意味着除了长度为0的单词外，对于所有其他单词它都能正常工作，对吗？ - Vishal K

Answer 6

检查回文的最简单方法。

private static String palindromic(String word) {
    if (word.length() <= 1) {
        return "Polidramic";
    }else if (word.charAt(0) != word.charAt(word.length() - 1)) {
        return "Not Polidramic";
    }
    return palindromic(word.substring(1, word.length() - 1));
} 

- Samet ÖZTOPRAK