Java中使用递归的最长回文

Question

我试图用递归得到一个字符串中最长的回文。以下是我的代码:

public class longestPalindrome{

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.println("Please enter a string: ");
        String sentence = "iprefer";            //replace with input.nextLine();

        System.out.println();

        longestPalindrome(sentence, sentence, 1, 1, 0, 0);
    }
//                                                                          1           1                   0               0
    private static void longestPalindrome(String str, String ORIGINAL, int level, int possibilities, int counter, int removedChars) {      
        if (str.replaceAll("[^a-zA-Z]", "").toLowerCase().equals(new StringBuffer(str).reverse().toString().replaceAll("[^a-zA-Z]", "").toLowerCase()) && str.length() >= 3) {
            System.out.println("The longest palindrome in the string is:" + str);
        }
        else if (str.length() < 3) {
            System.out.println("A palindrome of three characters or more does not exist in the string.");
        }
        else if (possibilities < level) {
            longestPalindrome(str.substring(counter, (ORIGINAL.length() - removedChars) + counter), ORIGINAL, level, ++possibilities, ++counter, removedChars);
        }
        else {
            longestPalindrome(ORIGINAL, ORIGINAL, ++level, 0, 0, ++removedChars);
        }
    }
}

所以这段代码并不完全有效，我不知道如何解决它。这是我的解释：

假设输入字符串是：“i更喜欢”。

我检查它的方法是：

一个展示的图像

这个字符串中最长的回文是“refer”。

我将遍历我的代码：

句子被发送到回文函数。

 if (str.replaceAll("[^a-zA-Z]", "").toLowerCase().equals(new StringBuffer(str).reverse().toString().replaceAll("[^a-zA-Z]", "").toLowerCase()) && str.length() >= 3) {
     System.out.println("The longest palindrome in the string is:" + str);
 }

这个if语句是为了检查字符串是否是回文。我不更改实际字符串，因为我想完全返回原始字符串。我替换所有空格并使其小写，并检查它是否是回文。如果不是：

 else if (str.length() < 3) {
      System.out.println("A palindrome of three characters or more does not exist in the string.");
 }

我检查字符串 （str） 的长度是否少于 3 个字符。如果是这样，则不存在回文。如果它的长度大于或等于 3 个字符，我继续递归语句。

 else if (possibilities < level) {
      longestPalindrome(str.substring(counter, (ORIGINAL.length() - removedChars) + counter), ORIGINAL, level, ++possibilities, ++counter, removedChars);
 }

这就是解释变得复杂的地方。每增加一个级别，可能性的数量就增加一个。例如，在第1级，有1种可能性。在第2级，有两种可能性，依此类推。因此，我们可以得出结论，可能性的#=级别。如果可能性的数量

 else {
      longestPalindrome(ORIGINAL, ORIGINAL, ++level, 0, 0, ++removedChars);
 }

我重置了所有值，但我增加了级别和删除字符的数量。

我不确定这个解释是否有意义，但是我可以澄清是否有问题。问题是:代码没有像预期的那样工作。我已经按照我认为它会执行的方式检查了代码，它在我的大脑中工作。我已经尝试使用调试器来解决问题，但我不能。我是来寻求帮助的。我还在学习java，所以如果我的代码中有任何愚蠢的错误，请原谅我。谢谢你的帮助！

编辑：这是字符串的当前输出：

 iprefer
 iprefer
 iprefe
 Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out           of range: 7
at java.lang.String.substring(String.java:1907)
at recursionq61.RecursionQ61.longestPalindrome(RecursionQ61.java:30)
at recursionq61.RecursionQ61.longestPalindrome(RecursionQ61.java:30)
at recursionq61.RecursionQ61.longestPalindrome(RecursionQ61.java:33)
at recursionq61.RecursionQ61.main(RecursionQ61.java:16)
 Java Result: 1

编辑2:我被禁止使用循环。

编辑3:好吧，看来我想通了。

public class RecursionQ61 {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.println("Please enter a string: ");
        String sentence = "i prefer pi";            //input.nextLine();

        System.out.println();

        longestPalindrome(sentence, sentence, 1, 1, 0, 0);
    }
//                                                                          1           1                   0               0
    private static void longestPalindrome(String str, String ORIGINAL, int level, int possibilities, int counter, int removedChars)   {

        System.out.println(str);

        if (str.replaceAll("[^a-zA-Z]", "").toLowerCase().equals(new StringBuffer(str).reverse().toString().replaceAll("[^a-zA-Z]", "").toLowerCase()) && str.length() >= 3) {
            System.out.println("The longest palindrome in the string is:" + str);
        }
        else if (str.length() < 3) {
            System.out.println("A palindrome of three characters or more does not exist in the string.");
        }
        else if (possibilities < level) {
            longestPalindrome(ORIGINAL.substring(counter, (ORIGINAL.length() - removedChars) + counter), ORIGINAL, level, ++possibilities, ++counter, removedChars);
        }
        else {
            longestPalindrome(ORIGINAL, ORIGINAL, ++level, 0, 0, ++removedChars);
        }
    }
}

我不得不将str.substring（counter， （str.length（） - removedChars） counter）更改为ORIGINAL.substring（counter， （ORIGINAL.length（） - removedChars） counter）。

Answer 1

我不清楚您在上面代码中的方法是什么，所以我将建议几种通用方法来编写需要使用递归的程序。

1）使用循环编写程序并使其工作。然后您可以将所有循环更改为递归方法，以一种相当机械的方式，尽管有点乏味。这不会证明对递归的理解，但对于分配来说可能已经足够好了，尤其是当分配是递归一开始就不合适的时候。

我将剽窃Old Curmudgeon的一些代码来演示：

int delta = 1;
// Walk outward from the pos - stop when the characters do not match.
while (pos - delta > 0 && pos + delta < s.length() && s.charAt(pos - delta) == s.charAt(pos + delta)) {
    delta += 1;
}
return delta;

可以变成像这样的哑递归例程：

int recursiveMethod(int delta, int pos, String s) {
    if (pos - delta > 0 && pos + delta < s.length() && s.charAt(pos - delta) == s.charAt(pos + delta)) {
        return recursiveMethod(delta + 1, pos, s);
    } else {
        return delta;
    }
}

我真的不需要知道这是如何工作的，我所要做的就是弄清楚它本质上执行与而循环相同的步骤。

2）递归的本质是将问题分解成更小的部分。然后，通过解决较小的问题来解决问题，并使用这些较小问题的解决方案来确定较大问题的解决方案。

我能想到的“最长回文”的最简单方法是这样的：如果你有一个Strings，那么：

如果< code>s本身是一个回文，那么它是< code>s中最长的回文；

否则，最长的回文必须包含在移除了第一个字符的< code>s中，或者包含在移除了最后一个字符的< code>s中。因此，解决这两个子字符串的问题，然后选择较长的解决方案。

（您还需要一个基本大小写来停止递归，但由于每个长度为 1 的字符串都自动满足第一个测试，因此基本情况可以简单地处理自己。

这将解决问题，但效率非常低。您将多次解决相同的子问题。如果从 s = “abcdefg” 开始，递归方法将通过两条不同的路径在“bcdef”上调用两次，较小的子字符串将被解析更多次。在我的头顶上，我认为这是一个 O（2ⁿ） 或 O（n*2 n） 解决方案，而一个简单的循环算法将是 O（^{n 2}）。但是，当您被迫对不合适的问题使用递归时，就会发生这种情况。

Answer 2

我意识到这不是一个答案，因为您特别要求递归解决方案，但也许这表明迭代解决方案是多么简单和优雅。

我将尝试为您组合一个优雅的递归，但它可能看起来很像这样。

private int longestPalindrome(String s, int pos) {
    int delta = 1;
    // Walk outward from the pos - stop when the characters do not match.
    while (pos - delta > 0 && pos + delta < s.length() && s.charAt(pos - delta) == s.charAt(pos + delta)) {
        delta += 1;
    }
    return delta;
}

private String longestPalindrome(String s) {
    int longest = 0;
    int longestLocation = 0;
    for (int i = 0; i < s.length(); i++) {
        // How long is the longest palindrome centered here.
        int length = longestPalindrome(s, i);
        if (length > longest) {
            // Keep track of the longest.
            longest = length;
            longestLocation = i;
        }
    }
    return s.substring(longestLocation - (longest - 1), longestLocation + longest);
}

public void test() {
    System.out.println("Hello");
    String[] tests = new String[]{"iprefer", "madamimadam", "abcdefedcbxqy"};
    for (String test : tests) {
        System.out.println("longestPalindrome(" + test + ")=" + longestPalindrome(test));

    }

}

Answer 3

你没有说错误是什么。我运行了您的代码，得到了一个StringIndexOutOfBoundsException异常，因为< code >(ORIGINAL . length()-removed chars)counter 是7，ORIGINAL="iprefer "，counter=removedChars=1。字符串索引从0开始。

也就是说，我认为你的方法效率低下。与其从最长到最短测试候选解，不如尝试从最短到最长：最短的回文长度为1（单个字符）或2（两个相同的连续字符）。给定回文P，检查前字符和后字符是否相同，如果它们都是x，那么你找到了回文P'=xPx。继续增长回文，记住迄今为止你看到的最长回文。