5. 最长回文子串
题目要求:
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd"
输出："bb"提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成代码解析1：
以下是更加优化的最优质代码，使用 Manacher 算法实现：
```
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
char[] t = preProcess(s);
int n = t.length;
int[] p = new int[n];
int center = 0, right = 0;
for (int i = 1; i < n - 1; i++) {
if (right > i) {
p[i] = Math.min(right - i, p[2 * center - i]);
}
while (t[i + p[i] + 1] == t[i - p[i] - 1]) {
p[i]++;
}
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
}
int len = 0, centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (p[i] > len) {
len = p[i];
centerIndex = i;
}
}
int start = (centerIndex - len) / 2;
return s.substring(start, start + len);
}
private char[] preProcess(String s) {
int n = s.length();
char[] t = new char[n * 2 + 3];
t[0] = '$';
t[n * 2 + 2] = '@';
for (int i = 0; i < n; i++) {
t[i * 2 + 1] = '#';
t[i * 2 + 2] = s.charAt(i);
}
t[n * 2 + 1] = '#';
return t;
}
}
```
代码中的变量解释如下：
- `t` 是预处理后的字符串，加入了特殊字符 `'$'` 和 `'@'`，并且每个字符之间都插入了特殊字符 `'#'`。
- `n` 是预处理后的字符串的长度。
- `p` 数组表示以每个字符为中心的最大回文半径。
- `center` 表示最大回文半径所在的中心点。
- `right` 表示最大回文半径所在的右边界。
- `len` 表示最长回文子串的长度。
- `centerIndex` 表示中心位置。
具体实现过程如下：
1. 对字符串 `s` 进行预处理，将其转换成一个新的字符串 `t`。具体来说，将字符串 `s` 的每个字符之间都插入特殊字符 `'#'`，并在字符串的开头和结尾加上特殊字符 `'$'` 和 `'@'`。
2. 初始化 `p` 数组全为 0，`center` 和 `right` 都为 0。
3. 遍历字符串 `t`，对于每个中心点 `i`，计算其最大回文半径。
4. 如果当前中心点 `i` 在 `right` 的范围内，则将 `p[i]` 初始化为左右对称点 `2 * center - i` 的最大回文半径和离右端点 `right` 的距离之间的较小值，可以利用对称性加速计算过程。
5. 从当前中心点 `i` 向左右两侧扩展，直到无法扩展为止，计算当前中心点 `i` 的回文半径。
6. 如果当前中心点的回文半径超过了 `right` 的范围，则更新 `center` 和 `right` 的值为当前中心点 `i` 和其对应的右边界。
7. 遍历 `p` 数组，找到最大回文半径和其所对应的中心位置。
8. 通过中心位置和最大回文半径计算原字符串中的最长回文子串的起始位置和长度。
9. 返回原字符串中的最长回文子串。
Manacher 算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$，是目前已知最快的解法。代码解释2:
每一行的代码含义如下：
```
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
char[] t = preProcess(s); // 预处理字符串，得到预处理后的字符串 t
int n = t.length;
int[] p = new int[n]; // 用来记录以每个字符为中心的最大回文半径
int center = 0, right = 0; // center 和 right 分别表示当前最大回文半径所在的中心点和右边界
for (int i = 1; i < n - 1; i++) { // 循环遍历预处理后的字符串 t，计算每个中心点的最大回文半径
if (right > i) {
p[i] = Math.min(right - i, p[2 * center - i]);
// 利用对称性优化计算，p[i] 初始化为左右对称点的最大回文半径和离右端点 right 的距离之间的较小值
}
while (t[i + p[i] + 1] == t[i - p[i] - 1]) {
// 从中心点 i 向左右两侧扩展，直到无法扩展为止，计算当前中心点的回文半径 p[i]
p[i]++;
}
if (i + p[i] > right) {
// 如果当前中心点的回文半径超过了 right 的范围，就更新 center 和 right 的值为当前中心点 i 和其对应的右边界
center = i;
right = i + p[i];
}
}
int len = 0, centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
// 遍历 p 数组，找到最长回文子串的长度 len 和其所在的中心位置 centerIndex
if (p[i] > len) {
len = p[i];
centerIndex = i;
}
}
int start = (centerIndex - len) / 2;
// 根据中心位置和最长回文子串的长度计算原字符串中的最长回文子串的起始位置
return s.substring(start, start + len);
// 返回原字符串中的最长回文子串
}
private char[] preProcess(String s) {
// 预处理字符串，将其转换成一个新的字符串 t
int n = s.length();
char[] t = new char[n * 2 + 3];
t[0] = '$';
t[n * 2 + 2] = '@';
for (int i = 0; i < n; i++) {
t[i * 2 + 1] = '#';
t[i * 2 + 2] = s.charAt(i);
}
t[n * 2 + 1] = '#';
return t;
}
}
```
预处理字符串 `s` 后，处理成了一个新的字符串 `t`，其中在字符串的两端和每个字符之间都插入了特殊字符 `'$'` 和 `'@'`，以及特殊字符 `'#'`。例如，如果输入字符串 `s` 是 `"racecar"`，那么经过预处理后，新的字符串 `t` 就是 "$#r#a#c#e#c#a#r#@"。
Manacher 算法的核心思想是利用已经求得的回文半径信息，尽可能地减少回文半径的重复计算，从而实现对于字符串的线性时间求解。具体实现可以参考上面代码中的注释。6. N 字形变换
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I示例 3：
输入：s = "A", numRows = 1
输出："A"提示：
1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000代码解析1:
以下是使用字符数组模拟 Z 字形排列，并遍历字符串一次进行填充的最优解：
```
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1 || numRows >= s.length()) {
return s;
}
char[] chars = s.toCharArray();
char[] res = new char[chars.length];
int interval = 2 * numRows - 2;
int index = 0;
for (int i = 0; i < numRows; i++) {
int step = interval - 2 * i;
for (int j = i; j < chars.length; j += interval) {
res[index++] = chars[j];
if (step > 0 && step < interval && j + step < chars.length) {
res[index++] = chars[j + step];
}
}
}
return new String(res);
}
}
```
代码中的变量解释如下：
- `chars` 是原始字符串转换成的字符数组。
- `res` 是 Z 字形排列后的字符数组。
- `interval` 是每组字符的间隔，即每两个相邻行之间的字符个数。
- `index` 是填充字符数组 `res` 的下一个位置。
做法如下：
1. 判断边界条件，如果 numRows 为 1 或者大于等于字符串长度，则直接返回原字符串。
2. 初始化一个字符数组 `res`，大小和 `chars` 相同。
3. 计算相邻两行的字符间隔 `interval`。
4. 对于每一行 `i`，从 `i` 开始，以间隔 `interval` 遍历字符数组 `chars`，将当前字符放入 `res` 数组中，并检查是否需要将该行与下一行交替的字符也放入 `res` 数组。
5. 返回填充完毕的字符数组 `res` 所对应的字符串。
这种做法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$，其中 $n$ 是字符串 `s` 的长度。代码解析2：
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1 || numRows >= s.length()) {
// 边界条件，如果 numRows 为 1 或者大于等于字符串长度，则直接返回原字符串
return s;
}
char[] chars = s.toCharArray();
// 将原始字符串转换成字符数组
char[] res = new char[chars.length];
// 初始化字符数组 res，大小和 chars 相同
int interval = 2 * numRows - 2;
// 计算相邻两行的字符间隔 interval
int index = 0;
// 定义填充 res 数组的下一个位置
for (int i = 0; i < numRows; i++) {
// 从第 0 行开始遍历所有行
int step = interval - 2 * i;
// 计算该行与下一行交替的字符在 chars 数组中的下标差值
for (int j = i; j < chars.length; j += interval) {
// 遍历 chars 数组中以 interval 为间隔的字符
res[index++] = chars[j]; // 将当前字符放到 res 数组中
if (step > 0 && step < interval && j + step < chars.length) {
// 如果当前行和下一行交替的字符在 chars 数组中存在
res[index++] = chars[j + step];
// 将交替的字符也放到 res 数组中
}
}
}
return new String(res);
// 返回填充完毕的字符数组转换成的字符串
}
}
```
因为要将给定字符串根据指定的行数进行 Z 字形排列，并以从左到右，从上到下的顺序来读取字符，所以我们需要设置一个 `interval` 变量来记录相邻两行的字符间隔，以及一个 `step` 变量来记录该行与下一行交替的字符在字符数组中的下标差值。
我们对于每一行，都遍历以 `interval` 为间隔的字符，将当前行的字符和下一行的交替字符添加到目标字符数组 `res` 中。
最后，我们将填充完毕的字符数组 `res` 转换成字符串并返回。1. 第 1 行，定义一个类 `Solution`，表示我们要解决问题。
2. 第 2 行，定义一个公有方法 `convert`，该方法接收两个参数：一个字符串 `s` 和一个整数 `numRows`，表示给定字符串和指定的行数。方法将返回一个字符串，即将给定字符串根据指定的行数进行 Z 字形排列后的结果。
3. 第 3 ~ 5 行，判断边界条件，如果 `numRows` 为 1 或者大于等于字符串长度，则直接返回原字符串 `s`。
4. 第 7 行，将原始字符串 `s` 转换成一个字符数组 `chars`，方便后续处理。
5. 第 9 行，初始化一个字符数组 `res`，大小与 `chars` 相同，即需要填充的目标字符数组。
6. 第 11 行，计算相邻两行的字符间隔 `interval`，即每两个相邻行之间的字符数。
7. 第 13 行，定义一个变量 `index`，表示填充字符数组 `res` 的下一个位置。
8. 第 15 ~ 24 行，通过两个嵌套的循环来遍历所有的行和需要填充的字符。首先从第 0 行开始遍历所有行，再从当前行的第一个字符开始，以间隔 `interval` 遍历字符数组 `chars`，将当前遍历到的字符放入 `res` 数组中，并检查是否需要将该行与下一行交替的字符也放入 `res` 数组。
9. 第 17 行，计算当前行与下一行交替的字符在 `chars` 数组中的下标差值 `step`。
10. 第 19 ~ 24 行，以 `interval` 为间隔遍历字符数组 `chars`，将遍历到的字符添加到目标字符数组 `res` 中。如果当前行和下一行交替的字符在 `chars` 数组中也存在，则把它们也添加到 `res` 数组中。注意检查数组下标是否越界。
11. 第 29 行，将填充完毕的字符数组 `res` 转换成字符串，并将其作为方法的返回值。
综上所述，该方法的作用是将给定字符串根据指定的行数进行 Z 字形排列，然后以从左到右，从上到下的顺序来读取字符，并将读取结果组成新的字符串，时间复杂度为 $O(n)$，其中 $n$ 是字符串 `s` 的长度，空间复杂度为 $O(n)$。
