最短回文与递归解决问题

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

我在Ideone上粘贴了一些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)));
}