LeetCode题练习与总结：最短回文串--214

一、题目描述

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1：

输入：s = "aacecaaa"
输出："aaacecaaa"

示例 2：

输入：s = "abcd"
输出："dcbabcd"

提示：

0 <= s.length <= 5 * 10^4
s 仅由小写英文字母组成

二、解题思路

确定最长回文前缀：我们需要找到字符串s的最长回文前缀。这意味着从字符串的开始到某个位置i，这段子串是回文的。我们可以从字符串的末尾开始，向前遍历，同时检查当前的前缀是否为回文。
检查回文：为了检查一个子串是否为回文，我们可以使用一个辅助函数isPalindrome。这个函数会接收字符串s以及两个索引start和end，它会比较这两个索引指向的字符是否相同，然后向内移动索引，直到start和end相遇或者交叉。
构建最短回文串：当我们找到了最长的回文前缀，我们可以将剩余的后缀部分（从i+1到字符串末尾的部分）反转，然后将这个反转的后缀添加到原字符串s的前面。这样，我们就能得到一个最短的回文串。
避免递归：在此解法中，我们避免了递归，直接在找到最长回文前缀后构建最终的回文串。

以下是解题步骤：

初始化变量i为字符串s的长度减一。
从字符串的末尾开始，使用isPalindrome函数检查从字符串开始到索引i的子串是否为回文。
如果找到回文前缀，则获取从i+1到字符串末尾的后缀部分，并将其反转。
将反转的后缀添加到原字符串的前面，形成最短的回文串并返回。

三、具体代码

class Solution {public String shortestPalindrome(String s) {int n = s.length();// 从字符串末尾开始，寻找最长回文前缀for (int i = n - 1; i >= 0; i--) {// 如果找到了回文前缀if (isPalindrome(s, 0, i)) {// 获取剩余的后缀部分，并反转String reversedSuffix = new StringBuilder(s.substring(i + 1)).reverse().toString();// 拼接最短的回文串return reversedSuffix + s;}}// 如果没有找到回文前缀，直接返回原字符串（虽然根据题目条件，这种情况不会发生）return s;}// 辅助函数，判断字符串s在[start, end]范围内是否为回文串private boolean isPalindrome(String s, int start, int end) {while (start < end) {if (s.charAt(start++) != s.charAt(end--)) {return false;}}return true;}
}

这个实现的时间复杂度是O(n^2)，因为对于每个可能的回文前缀长度，我们都需要调用isPalindrome函数，该函数在最坏情况下会遍历一半的字符串。尽管时间复杂度仍然是平方级别的，但是我们已经避免了递归调用，这在实际运行时可能会更加高效。

四、时间复杂度和空间复杂度

1. 时间复杂度

主循环：外层循环从字符串末尾开始，每次递减，直到找到最长的回文前缀。这个循环的次数是n，其中n是字符串s的长度。
回文检查：在每次外层循环中，我们调用isPalindrome函数来检查从字符串的开始到当前位置i的子串是否为回文。在最坏的情况下，isPalindrome函数可能需要遍历半个字符串，即n/2次比较。因此，对于每个可能的回文前缀长度，我们都要进行n/2次比较。

综合以上两点，我们可以得到以下的时间复杂度计算：

对于第一个字符，isPalindrome函数执行0次比较。
对于第二个字符，isPalindrome函数执行1次比较。
…
对于第n个字符，isPalindrome函数执行(n-1)/2次比较。

总比较次数是0 + 1 + 2 + … + (n-1)/2，这是一个等差数列，其求和公式为(首项 + 末项) * 项数 / 2。在这里，项数是(n+1)/2，所以总比较次数是(0 + (n-1)/2) * (n+1)/2 / 2，简化后为(n^2 - n)/4，时间复杂度为O(n^2)。

2. 空间复杂度

辅助函数调用栈：isPalindrome函数是直接调用的，没有递归，所以没有额外的调用栈空间。
字符串反转：在找到最长回文前缀后，我们创建了一个新的字符串来保存反转的后缀。这个操作需要O(n)的空间，其中n是后缀的长度。
返回结果：最后返回的字符串是反转的后缀与原字符串拼接的结果，这需要O(n)的空间来存储。

综上所述，空间复杂度主要取决于字符串反转和最终结果字符串的存储，因此空间复杂度为O(n)。

五、总结知识点

字符串操作：
- length()：获取字符串的长度。
- charAt(int index)：获取字符串中指定索引位置的字符。
- substring(int start, int end)：获取字符串的子串，从指定起始索引到结束索引（不包括结束索引）。
StringBuilder类：
- StringBuilder(String str)：使用字符串初始化StringBuilder对象。
- reverse()：反转StringBuilder中的字符序列。
- toString()：将StringBuilder对象转换为字符串。
循环与条件判断：
- for循环：用于遍历字符串的每个字符。
- if语句：用于判断当前的前缀是否为回文。
递归与迭代：
- 尽管代码中没有使用递归，但提到了递归的概念，并避免了递归的使用，改为迭代方式来解决问题。
算法逻辑：
- 最长回文前缀：寻找字符串中最长的回文前缀，这是解题的关键步骤。
- 回文串检查：通过双指针方法检查一个字符串的子串是否为回文。
字符串拼接：
- 使用+操作符拼接字符串，这是Java中常见的字符串操作。
辅助函数：
- isPalindrome：定义了一个辅助函数来检查字符串的子串是否为回文，这有助于代码的模块化和重用。
算法优化：
- 避免不必要的计算：一旦找到最长的回文前缀，就立即停止循环，并开始构建最短回文串。