递归函数：检查 Java 中的回文
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15722624/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Recursive Function : Check for palindrome in Java
提问by choloboy7
I have a class that checks whether a string is a palindrome or not. I have two questions.
我有一个检查字符串是否为回文的类。我有两个问题。
1) Is this the most efficient way to check for palindrome? 2) Can this be implemented recursively?
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;
}
}
}
Have a test class to test this... Doubt its needed but here it is anyways if anyone cares to try it out to be able to help me with any of the two questions above...
有一个测试类来测试这个......怀疑它是否需要，但无论如何，如果有人愿意尝试它能够帮助我解决上述两个问题中的任何一个......
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");
}
}
}
thanks in advance for any help and or input :)
提前感谢您的任何帮助和/或输入:)
回答by recursion.ninja
To implement a 'palindrome check' recursively, you must compare if the first and last characters are the same. If they are not the same the string is most certainly not a palindrome. If they are the same the string might be a palindrome, you need to compare the 2nd character with the 2nd to last character, and so on until you have strictly less then 2 characters remaining to be checked in your string.
要以递归方式实现“回文检查”，您必须比较第一个和最后一个字符是否相同。如果它们不相同，则字符串肯定不是回文。如果它们相同，则字符串可能是回文，您需要将第二个字符与倒数第二个字符进行比较，依此类推，直到您的字符串中剩余的字符数严格少于 2 个。
A recursive algorithm would look like this:
递归算法如下所示：
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)); }
}
Note, that my recursionmethod is not most efficient approach, but simple to understand
Marimuthu Madasamyhas a more efficient recursivemethod, but is harder to understand
- Joe Fhas listed an equivalently efficient iterativemethod
which is the bestapproach for implementation because it cannot cause a stack overflowerror
请注意，我的递归方法不是最有效的方法，但易于理解
Marimuthu Madasamy有更高效的递归方法，但更难理解
- Joe F列出了一个等效有效的迭代方法
，这是实现的最佳方法，因为它不会导致堆栈溢出错误
回答by Marimuthu Madasamy
Here is another recursive solution but using array which could give you some performance advantage over string in recursive calls (avoiding substringor charAt).
这是另一种递归解决方案，但使用数组可以在递归调用（避免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);
}
The idea is that we keep track of two positions in the array, one at the beginning and another at the end and we keep moving the positions towards the center.
这个想法是我们跟踪数组中的两个位置，一个在开头，另一个在结尾，我们不断向中心移动这些位置。
When the positions overlap and pass, we are done comparing all the characters and all the characters so far have matched; the string is palindrome.
当位置重叠并通过时，我们完成了所有字符的比较，并且到目前为止所有字符都匹配；字符串是回文。
At each pass, we compare the characters and if they don't match then the string is not palindrome otherwise move the positions closer.
在每次通过时，我们比较字符，如果它们不匹配，则字符串不是回文，否则将位置移近。
回答by Joe F
It's actually sufficient to only check up to the middle character to confirm that it is a palindrome, which means you can simplify it down to something like this:
实际上，仅检查中间字符以确认它是回文就足够了，这意味着您可以将其简化为如下所示：
// 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;
A recursive solution is very possible but it is not going to give you any performance benefit (and probably isn't as readable).
递归解决方案是非常可能的，但它不会给您带来任何性能优势（并且可能不那么可读）。
回答by Vishal K
Can this be implemented Recursively?
这可以递归实现吗？
YES
Here is example:
是
这里是例子：
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;
}
回答by Hlodowig
My two cents. It's always nice to see the different ways people solve a problem. Of course this is not the most efficient algorithm memory or speed wise.
我的两分钱。看到人们解决问题的不同方式总是很高兴的。当然，这不是最有效的算法内存或速度。
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;
}
回答by Samet ?ZTOPRAK
The simplest way to check palindrome.
检查回文的最简单方法。
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));
}
