我有一个类检查字符串是否是回文。我有两个问题。
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");
}
}
}
提前感谢您的任何帮助和/或意见:)
要递归地实现“回文检查”，您必须比较第一个和最后一个字符是否相同。如果它们不相同，则该字符串肯定不是回文串。如果它们相同，则字符串可能是回文，您需要将第二个字符与倒数第二个字符进行比较，依此类推，直到字符串中剩余的待检查字符严格少于 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有更高效的递归方法，但更难理解
这是另一种递归解决方案，但使用数组可以在递归调用中比字符串提供一些性能优势（避免
substringcharAtprivate 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);
}
我们的想法是，我们跟踪数组中的两个位置，一个在开头，另一个在结尾，并且我们不断将位置移向中心。
当位置重叠并通过时，我们就完成了所有字符的比较，并且到目前为止所有字符都已匹配；该字符串是回文。
在每次传递时，我们都会比较字符，如果它们不匹配，则该字符串不是回文，否则将位置移近。
实际上只检查中间字符以确认它是回文就足够了，这意味着您可以将其简化为如下所示：
// 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;
递归解决方案是很有可能的，但它不会给您带来任何性能优势（并且可能不那么可读）。
这可以递归实现吗？
是
这是例子：
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;
}
我的两分钱。看到人们解决问题的不同方式总是令人高兴。当然，这不是最有效的算法内存或速度。
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;
}
最简单的回文检查方法。
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));
}
更优化的解决方案是将字符串转换为字符数组，然后递归检查
fun solve(A: String): Int {
return if (solveUtil(A.toCharArray(), 0, A.length - 1)) 1 else 0
}
fun solveUtil(A: CharArray, start: Int, end: Int): Boolean {
if (start >= end) {
return true
}
return A[start] == A[end] && solveUtil(A, start + 1, end - 1)
}