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

Question

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

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

例如：

给定 "aacecaaa", return "aaacecaaa".

给定 "abcd", return "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();  
}

我在 Ideone here

上粘贴了一些实现 isPalindrome 的测试用例

Answer 2

public String shortestPalindrome(String s) {
   String returnString ="";
   int h = s.length()-1;
    if(checkPalindrome(s))
    {
        return s;
    }
    while(h>=0)
    {
       returnString =returnString + s.charAt(h);
       if(checkPalindrome(returnString+s))
       {
           return returnString+s;
       }
        h--;
             
    }
    return returnString+s;
       
}

public boolean checkPalindrome(String s)
{
    int midpoint = s.length()/2;
    // If the string length is odd, we do not need to check the central character
    // as it is common to both
    return (new StringBuilder(s.substring(0, midpoint)).reverse().toString()
            .equals(s.substring(s.length() - midpoint)));
}

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

Shortest Palindrome with recursive solution issue

java

algorithm

palindrome