一、题目

　　1、审题

　　

　　2、分析

　　　　给出一个字符串，在此字符串前边添加字符，使得其成为一个回文，求添加最少字符后，所形成的回文。

 

二、解答

　　1、思路：

　　　　方法一、

　　　　①、为了处理回文字符数为奇数和偶数的问题，先在字符串 s 的每一个字符之间插入字符 '#'，并将每个字符放入一个 List 中

　　　　②、下标 index 依次从 1 到 mid，定义两个指针 left = index - 1、right = index + 1；

　　　　　　比较 left 、right 所指元素是否相等，若不相等，则 index 向后移动，若相等，则 left、right相反移动，直到 left < 0，此时，即为以 index 为中心，形成的字符串为回文。记录最大的回文中心的字符下标 index

　　　　③、将 ②所求得的最大 index 为中心的字符串所不包含的 s 的后部分子字符串逆序插入一个 StringBuilder 中，并将 s 插入 此 StringBuilder 中，返回。

1    public String shortestPalindrome(String s) { 2          3         List
     
       list = new ArrayList<>(); 4         list.add('#'); 5         for(char c: s.toCharArray()) { 6             list.add(c); 7             list.add('#'); 8         } 9 10         int len = list.size();11         int mid = (len - 1) / 2;12         int i = 1;13         int max = 0;14         while(i <= mid) {15             int left = i - 1;16             int right = i + 1;17             while(left >= 0 && right <= len - 1) {18                 if(list.get(left) != list.get(right))19                     break;20                 left--;21                 right++;22             }23             if(left <= 0)24                 max = i;25             i++;26         }27         max = max * 2 + 1;28         StringBuilder sb = new StringBuilder();29         for (int j = len - 1; j >= max; j--) {30             if(list.get(j) != '#')31                 sb.append(list.get(j));32         }33         sb = sb.append(s);34         return sb.toString();35     }
     

 　　

　　方法二、

　　　　采用 KMP 的 Next 数组。

　　　　①、构造新的字符串 tmp = s + '#' + s.reverse + ‘_’； 

　　　　②、求出 tmp 的 KMP 算法的 Next 数组。其中 next 的最后一个元素对应的字符是 ‘_’ ，代表 ‘_’ 之前的字符串能匹配的最长前缀后缀长度 len。

　　　　　　'#' 的作用是使得 '_' 对应的 next 数组值 len 不超过 s 的长度。

　　　　③、所求的最短回文即为： s 下标 从 len 开始的后部分子串翻转 + s 。

以 aacecaaa 为例：

1     public String shortestPalindrome2(String s) { 2          3         String tmp = s + "#" + new StringBuffer(s).reverse().toString() + "_"; 4         int[] table = getTable(tmp); 5          6         return new StringBuffer(s.substring(table[table.length - 1])).reverse().toString() + s; 7     } 8      9     10     private int[] getTable(String s) {11         int[] next = new int[s.length()];12         next[0] = -1;13         int k = -1;14         int j = 0;15         while(j < s.length() - 1) {16             if(k == -1 || s.charAt(k) == s.charAt(j)) {17                 ++k;18                 ++j;19                 next[j] = k;20             }21             else {22                 k = next[k];23             }24         }25         26         return next;27     }

 

　　方法三、

　　　　采用递归

　　　　①、找出从下标 0 开始的可能最大回文 str1，则 s 剩下子串为 str2；

　　　　②、str3 是 str2 的翻转，继续递归 str1，直到可以确定 str1 为一个回文，则返回的结果为 str3 + str1 + str2；

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

　　

　　方法四、

　　　　采用循环，判断  s 从下标 0 开始的构成的最大回文子串 str，最终将 s 中剩下的末尾的不包含在 str 中的子串进行翻转并 加上 s 返回即可。

1     public String shortestPalindrome4(String s) { 2         int i = 0, end = s.length() - 1, j = end; 3         char chs[] = s.toCharArray(); 4         while(i < j) { 5             if(chs[i] == chs[j]) { 6                 i++; 7                 j--; 8             } 9             else {10                 i = 0;11                 j = --end;12             }13         }14         return new StringBuilder(s.substring(end + 1)).reverse().toString() + s;15     }