4

我有一个检查字符串是否为回文的类。我有两个问题。

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

    }

}

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

4

6 回答 6

7

要递归实现“回文检查”，您必须比较第一个字符和最后一个字符是否相同。如果它们不相同，则字符串肯定不是回文。如果它们相同，则字符串可能是回文，您需要将第 2 个字符与倒数第 2 个字符进行比较，依此类推，直到您的字符串中要检查的字符严格少于 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列出了一种等效有效的迭代方法
    ，这是最好的实现方法，因为它不会导致堆栈溢出错误
于 2013-03-30T19:39:20.313 回答
6

这是另一种递归解决方案，但使用数组可以在递归调用中为您提供优于字符串的性能优势（避免substringor 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);
}

The idea is that we keep track of two positions in the array, one at the beginning and another at the end and we keep moving the positions towards the center.

When the positions overlap and pass, we are done comparing all the characters and all the characters so far have matched; the string is palindrome.

At each pass, we compare the characters and if they don't match then the string is not palindrome otherwise move the positions closer.

于 2013-03-30T20:05:02.617 回答
5

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

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

递归解决方案是非常可能的，但它不会给您带来任何性能优势（并且可能不那么可读）。

于 2013-03-30T19:42:25.150 回答
1

这可以递归实现吗？

是
这里是例子：

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;
}
于 2013-03-30T19:54:54.070 回答
1

My two cents. It's always nice to see the different ways people solve a problem. Of course this is not the most efficient algorithm memory or speed wise.

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;
}
于 2014-03-21T06:00:25.423 回答
0

The simplest way to check palindrome.

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));
}
于 2019-07-03T11:12:08.407 回答