递归函数:检查Java中的回文
递归函数:检查Java中的回文
提问于 2013-03-31 03:32:43
我有一个检查字符串是否为回文的类。我有两个问题。
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");
}
}
}提前感谢您的帮助和/或输入:)
回答 6
Stack Overflow用户
回答已采纳
发布于 2013-03-31 03:39:20
要以递归方式实现“回文检查”，必须比较第一个字符和最后一个字符是否相同。如果它们不相同，那么这个字符串肯定不是回文。如果它们相同，则字符串可能是回文，您需要将第二个字符与倒数第二个字符进行比较，依此类推，直到您的字符串中需要检查的字符严格少于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)); }
}请注意，我的递归方法不是最有效的方法，但simple to understand
- 有一种更有效的递归方法，但更难understand
- 列出了一种等效的高效迭代方法
以下哪种方法是实现的最佳方法，因为它不会导致出现stack overflow错误
Stack Overflow用户
发布于 2013-03-31 04:05:03
这是另一个递归解决方案，但是使用数组可以在递归调用中提供比字符串更好的性能(避免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);
}这个想法是，我们跟踪数组中的两个位置，一个在开始，另一个在结束，我们不断向中心移动位置。
当位置重叠并通过时，我们完成了所有字符的比较，并且到目前为止所有字符都匹配了；字符串是回文字符串。
在每一遍中，我们比较字符，如果它们不匹配，则字符串不是回文，否则将位置移动得更近。
Stack Overflow用户
发布于 2013-03-31 03:42:25
实际上，只需检查中间字符以确认它是一个回文字符就足够了，这意味着您可以将其简化为如下所示：
// 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;递归解决方案是非常有可能的，但是它不会给你带来任何性能上的好处(而且可能不是那么好读)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15722624
复制相关文章
相似问题
腾讯云开发者
