LeetCode 5. Longest Palindromic Substring [Medium]

发表于 2020-01-30 更新于 2024-08-05 分类于 LeetCode ， Medium 阅读次数：

题目难度：Medium

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1 2	Input: "cbbd" Output: "bb"

使用 S 表示原字符串

使用 T 表示转换过后的字符串

使用 C 表示目前已知的子回文串中，右边界的位置最大的那个子回文串的中心。

使用 R 表示以 C 为中心的回文串的最右端的位置。

使用 i 表示 T 中正要确定回文串长度的一个位置。

使用 i’ 表示以 C 为中心，i 的对称位置

假设字符串 S 为 babcbabcbaccba

转换为字符串 T：#b#a#b#c#b#a#b#c#b#a#c#c#b#a#

考虑以下三种情况：

情况1：i’ 的回文串的左边界不超过 C 的回文串的左边界。

这种情况下，P[i] = P[i’]

情况2：i’ 的回文串的左边界超过了 C 的回文串的左边界。

这种情况下，i 的右边界不可能超过 C 的右边界，因为如果 i 的右边界超过了 C 的右边界，则证明 C 的回文串的长度还能更长。

情况3：i’ 的回文串的左边界和 C 的回文串的左边界相同。