给你一个字符串 s
,找到 s
中最长的回文子串。
回文子串是指一个字符串中的子序列,该子序列正读和反读都是一样的。比如 “level”,“abccba”
解题思路
要找到一个字符串中的最长回文子串,可以采用中心扩展法。这种方法的基本思想是从字符串的每个字符(以及每对相邻字符)出发,向两边扩展,直到不再是回文为止。这样可以找到以每个字符为中心的所有回文子串,并从中选出最长的那个。
解题步骤
- 边界情况处理:如果字符串长度小于等于1,直接返回原字符串。
- 初始化变量:定义变量
max
来临时存储最长回文子串。 - 遍历字符串:对于每个字符,尝试两种情况:
- 以该字符为中心的回文子串(奇数长度)
- 以该字符及其右边的字符为中心的回文子串(偶数长度)
- 扩展回文子串:使用双指针
left
和right
向两边扩展,检查是否仍然是回文。 - 记录最长回文子串:如果
helper
返回的回文子串比已知的最长回文子串还要长,更新max
。 - 返回结果:遍历结束后返回
max
。
typescript代码实现
/**
* @param {string} s
* @return {string}
*/
const longestPalindrome = (s: string) => {
if (s.length < 2) return s; // 边界条件
let max: string = ""; // 存储最长回文子串
for (let i = 0; i < s.length; i++) {
helper(i, i); // 考虑奇数长度
helper(i, i + 1); // 考虑偶数长度
}
// 辅助函数,寻找回文子串
function helper(l: number, r: number) {
while (l >= 0 && r <= s.length - 1 && s[l] === s[r]) {
l--; // 向左扩展
r++; // 向右扩展
}
const maxStr = s.slice(l + 1, r + 1 - 1);
if (maxStr.length > max.length) max = maxStr;
}
return max;
};
此算法的时间复杂度为 O(n^2)
其中 n 是字符串的长度,因为需要对每个字符尝试构建回文子串并进行比较。空间复杂度为 O(1)
。
本文为原创,未经授权,禁止任何媒体或个人自媒体转载
商业侵权必究,如需授权请联系340443366@qq.com