递归检查回文

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列出了一种等效的迭代方法
  ,这是实现的最佳方法,因为它不会导致堆栈溢出错误

Answer 2

这是另一个递归解决方案,但使用数组可以在递归调用(避免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 3

实际上只需检查中间字符以确认它是回文就足够了,这意味着您可以将其简化为类似下面的内容:

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

递归解决方案是非常可能的,但它不会给您任何性能优势(并且可能不具有可读性).