大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个字符串，通过在字符串前面添加字符转换为回文串，找到并返回转换的最短回文串。”
2、题目描述
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1： 输入： s = "aacecaaa" 输出： "aaacecaaa"
示例 2： 输入： s = "abcd" 输出： "dcbabcd"
二、解题
1、思路分析
这道题要求给定一字符串，将字符串添加字符转为为回文串，返回这种方法转换的最短回文串。
这道题可以等价于找到字符串的最长回文前缀，比如 s = "aacecaaa" 的最长回文前缀为 "aacecaa"， 那么将其作为最终回文串的中心，再反转后面的非回文串放到前面即可。
回文是指正反方向读起来都一样的字符串，字符串s[0]是字符串的s的最短回文前缀。
可以发现不论是怎样的字符串，都至少存在一个字符可以作为回文串的中心，比如 "abcd" 中 a可以作为中心。
最长的回文前缀这个回文串的中心一定小于 (n+1)/2，而且回文串的左边界需要刚好达到字符串的开头，可以使用中心扩展法，枚举将0 ~ (n+1)/2内的值 作为中心的 所有回文串，找到最长的回文前缀。
2、代码实现
代码参考：
class Solution { public String shortestPalindrome(String s) { char[] arr = s.toCharArray(); int n = arr.length; if(n == 0) { return ""; } int max = -1; for(int i = 0; i < (n + 1) / 2; ++i) { int len1 = expand(arr, i, i); int len2 = expand(arr, i, i + 1); int len = Math.max(len1, len2); // 回文串的长度刚好可以到达左边界 0 if(i - (len - 1) / 2 == 0) { max = Math.max(max, len); } } String last = s.substring(max); return new StringBuilder(last).reverse() + s.substring(0, max) + last; } // 中心扩展 public int expand(char[] arr, int l, int r) { while(l >= 0 && r < arr.length && arr[l] == arr[r]) { l--; r++; } return r - l - 1; } }
3、时间复杂度
时间复杂度：O(|s|)
其中s是字符串的长度。
空间复杂度：O(1)
只需要常数级的变量空间。
三、总结
总结一下：
无论是怎样的字符串，都存在一个字符可以作为回文串的中心。
先找到这个中心，然后回文串的左边界需要达到字符串的开头。
使用中心拓展法枚举这种中心的(n+1)/2的边界内的所有值，判断可以作为中心的所有回文串。
找到最长的回文前缀。
