最短的迴文遞歸解決方案問題

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