递归检查回文
我有一个类来检查字符串是否是回文。 我有两个问题。
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("wow") == 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有一种更有效的递归方法，但更难理解
- Joe F列出了一种等效的迭代方法
这是实现的最佳方法，因为它不会导致堆栈溢出错误
这是另一个递归解决方案，但是使用数组可以在递归调用中为字符串提供一些性能优势（避免使用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); }
我们的想法是，我们跟踪arrays中的两个位置，一个位于开头，另一个位于末尾，我们继续将位置移向中心。
当位置重叠并通过时，我们将比较所有字符和到目前为止匹配的所有字符; 字符串是回文。
在每次通过时，我们比较字符，如果它们不匹配则字符串不是回文，否则移动位置更近。
实际上只需检查中间字符以确认它是回文就足够了，这意味着您可以将其简化为如下所示：
// 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; }