递归检查回文

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"); 
    } 

    } 

} 

在此先感谢您的帮助和或输入:)

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错误

Answer 2

它实际上足以只检查到中间字符以确认它是回文，这意味着您可以将其简化为如下所示：

// 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; 

递归解决方案是非常有可能的，但它不会给你带来任何性能上的好处（并且可能不可读）。

Answer 3

这是可以实现递归吗？

YES
这里是例如：

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; 
} 

Answer 4

这里是另一个递归溶液，但使用阵列，其可以给你超过在递归调用字符串一些性能优点（避免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); 
} 

的想法是，我们跟踪阵列中的两个位置，一个在开头，另一个在年底，我们不断走向中心的位置。

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

在每次通过时，我们比较字符，如果它们不匹配，则字符串不是回文，否则将位置移近。

Answer 5

我的两分钱。看到人们解决问题的不同方式总是令人高兴的。当然，这不是最有效的算法内存或速度方面。

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; 
}