java - 具有递归解决方案问题的最短回文

Question

调试下面的问题(一个递归的解法)，弄糊涂了for循环的逻辑意义是什么。如果有人有任何见解，感谢分享。

给定一个字符串 S，您可以通过在其前面添加字符将其转换为回文。通过执行此转换找到并返回您可以找到的最短回文。

例如:

给定“aacecaaa”，返回“aaacecaaa”。

给定“abcd”，返回“dcbabcd”。

int j = 0;
for (int i = s.length() - 1; i >= 0; i--) {
    if (s.charAt(i) == s.charAt(j)) { j += 1; }
}
if (j == s.length()) { return s; }
String suffix = s.substring(j);
return new StringBuffer(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;

基于 KMP 的解决方案，

public class Solution {
    public String shortestPalindrome(String s) {
        String p = new StringBuffer(s).reverse().toString();
        char pp[] = p.toCharArray();
        char ss[] = s.toCharArray();
        int m = ss.length;
        if (m == 0) return "";

        // trying to find the greatest overlap of pp[] and ss[]
        // using the buildLPS() method of KMP
        int lps[] = buildLPS(ss);
        int i=0;// points to pp[]
        int len = 0; //points to ss[]

        while(i<m) {
            if (pp[i] == ss[len]) {
                i++;
                len++;
                if (i == m)
                    break;
            } else {
                if (len == 0) {
                    i++;
                } else {
                    len = lps[len-1];
                }
            }
        }
        // after the loop, len is the overlap of the suffix of pp and prefix of ss
        return new String(pp) + s.substring(len, m);

    }

    int [] buildLPS(char ss[]) {
        int m = ss.length;
        int lps[] = new int[m];
        int len = 0;
        int i = 1;
        lps[0] = 0;
        while(i < m) {
            if (ss[i] == ss[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len == 0) {
                    i++;
                } else {
                    len = lps[len-1];
                }

            }
        }

        return lps;
    }
}

提前致谢， 林

Answer 1

除了使用 j 之外，我的原始评论是不正确的 - 正如您所指出的'检查是否s是一个完整的回文，j也用于查找(智能地猜测？)围绕其环绕的索引 + 反转可能存在于字符串开头的最长回文的尾随字符。我对算法的理解如下:

例如aacecaaa给出 j = 7 , 导致

`aacecaaa` is `aacecaa` (palindrome) + `a` (suffix)

所以附加到开头的最短回文是:

`a` (suffix) + `aacecaa` + `a` (suffix)

如果后缀由多个字符组成，则必须将其反转:

`aacecaaab` is `aacecaa` (palindrome) + `ab` (suffix)

所以在这种情况下的解决方案是:

`ba` + `aacecaa` + `ab` (suffix)

在最坏的情况下 j = 1 (因为 a 将匹配 i=0 和 j=0 )，例如abcd里面没有回文序列，所以最好的办法是环绕第一个字符

dcb + a + bcd

老实说，我不是 100% 确信您正在调试的算法在所有情况下都能正常工作，但似乎找不到失败的测试用例。该算法当然不直观。

编辑

我相信最短的回文可以确定地导出，根本不需要递归 - 似乎在您正在调试的算法中，递归掩盖了 j 值的副作用。在我看来，这是一种确定 j 的方法以更直观的方式:

private static String shortestPalindrome(String s) {
    int j = s.length();
    while (!isPalindrome(s.substring(0, j))) {
        j--;
    }
     String suffix = s.substring(j);
    // Similar to OP's original code, excluding the recursion.
    return new StringBuilder(suffix).reverse()
              .append(s.substring(0, j))
              .append(suffix)
              .toString();  
}

我已经粘贴了一些带有 isPalindrome 实现的测试用例在 Ideone here