问题：
给定一个字符串s，可以通过在字符串前面添加字符将,其转换为回文串。找到并返回可以用这种方式转换的最短,回文串。
示例1：,输入：s="aacecaaa",输出："aaacecaaa"。
示例2：,输入：s="abcd",输出：“dcbabcd"。提示：,·0<=s.length<=5*104,·s仅由小写英文字母组成。
解答思路：
以下是一个使用 Java 语言实现的解决方案：
public class ShortestPalindrome {
public String shortestPalindrome(String s) {
int n = s.length();
for (int i = n - 1; i >= 0; i--) {
if (isPalindrome(s, 0, i)) {
String suffix = s.substring(i + 1);
return new StringBuilder(suffix).reverse().append(s).toString();
}
}
return "";
}
private boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start++)!= s.charAt(end--)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
ShortestPalindrome sp = new ShortestPalindrome();
String s1 = "aacecaaa";
String s2 = "abcd";
System.out.println(sp.shortestPalindrome(s1));
System.out.println(sp.shortestPalindrome(s2));
}
}这个算法的时间复杂度为 O(n^2)，其中 n 是输入字符串的长度。在最坏情况下，我们需要遍历字符串的每一个字符来判断是否为回文。空间复杂度为 O(1)，我们只使用了固定的额外空间。
(文章为作者在学习java过程中的一些个人体会总结和借鉴，如有不当、错误的地方，请各位大佬批评指正，定当努力改正，如有侵权请联系作者删帖。)