🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻 🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜 🌲 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题 🌲 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧🧐！ 🌲 今天是力扣算法题持续打卡第5天🎈！ 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
示例 2：
输入：s = “cbbd”
示例 3：
输入：s = “a”
示例 4：
输入：s = “ac”
提示：
1 <= s.length <= 1000 s 仅由数字和英文字母（大写和/或小写）组成 这里简单解释一下什么是回文串~
"回文串”就是一个正读和反读都一样的字符串，比如“mom”或者“noon”等等就是回文串。
顾名思义，“回文子串”的意思是一个字符串中的回文串，比如字符串“baba”中就包含有“bab”和“aba”这两个回文子串
解题思路
首先我们会想到使用 暴力法 来解决题目，用3层循环来对每个子串进行检查，最后取最长的子串作为结果，这样时间复杂度为 O(n^3) 。
public class Solution {
public string LongestPalindrome ( string )
{
string = "" ;
int = s. Length;
for ( int = 0 ; i < n; i++ )
{
for ( int = i; j < n; j++ )
{
// 检查 s[i]到s[j]是否是回文串，如果是，且长度大于result长度，就更新它
int = i, q = j;
bool = true ;
while ( p < q)
{
if ( s[ p++ ] != s[ q-- ] )
{
isPalindromic = false ;
break ;
}
}
if ( isPalindromic)
{
int = j - i + 1 ;
if ( len > result. Length)
{
result = s. Substring ( i, len) ;
}
}
}
}
return result;
}
}
链接：https: / / leetcode- cn. com/ problems/ longest- palindromic- substring/ solution/ leetcode- 5 - longest- palindromic- substring- zui- chang/
执行结果
复杂度分析
时间复杂度： O(n^3)
对于回文串，我们可以找到一个中心，从这个中心向两边扩展的话，两边对应的值是相等的。按照这个逻辑，我们只需要一层主循环 i 将 s 遍历一遍即可,并在循环内部 将s[i]视为中心 使用中心扩展法来求出以s[i]为中心的最长的回文串；当i将s遍历完后，即可得到s的最长回文串。
下面我们以 s=“abcbc”, 且 i==2 为例，讨论一下如何进行中心扩展。
i==2指向c，我们初始化两个指针p与q都指向这个c p–，q++，p指向了左边b，q指向了右边b 因为s[p]==s[q], 所以再次执行p–,q++,此时p指向了最左边a，q指向了最右边c 因为s[p]!=s[q],所以结束扩展。
此时，我们得到了当i指向中间c时的最长回文子串为"bcb",长度为 q-p-1,开始位置为p+1. 对应图解图下：
当子串长度为奇数时，这个逻辑很容易理解； 当子串长度为偶数时，比如 “abba”，我们需要把中心理解为中轴线，即中轴线在两个b的中间。
将中心理解为中轴线后，中轴线既可以在整数位上，例如"aba"中的b，也可以在两数之间，例如"abba"中的bb之间。若我们用mid表示中轴线，则mid可以等于0、1、2… 也可以等于0.5、1.5、2.5… 对于长度为n的数组，中轴线的选择有 n 个，i 的取值为0到 2(n-1) .。
代码为：
public class Solution {
public string LongestPalindrome ( string )
{
string = "" ;
int = s. Length;
int = 2 * n - 1 ;
for ( int = 0 ; i < end; i ++ )
{
double = i / 2.0 ;
int = ( int ) ( Math. Floor ( mid) ) ;
int = ( int ) ( Math. Ceiling ( mid) ) ;
while ( p >= 0 && q < n)
{
if ( s[ p] != s[ q] ) break ;
p-- ; q++ ;
}
int = q - p - 1 ;
if ( len > result. Length)
result = s. Substring ( p + 1 , len) ;
}
return result;
}
}
链接：https: / / leetcode- cn. com/ problems/ longest- palindromic- substring/ solution/ leetcode- 5 - longest- palindromic- substring- zui- chang/
执行结果
复杂度分析
时间复杂度： O(n^2)
Java方法也是力扣官方对此题的解答，可以参考答案
public class Solution {
public String longestPalindrome ( String s) {
int len = s. length ( ) ;
if ( len < 2 ) {
return s;
}
int maxLen = 1 ;
int begin = 0 ;
// dp[i][j] 表示 s[i..j] 是否是回文串
boolean [ ] [ ] dp = new boolean [ len] [ len] ;
// 初始化：所有长度为 1 的子串都是回文串
for ( int i = 0 ; i < len; i++ ) {
dp[ i] [ i] = true ;
}
char [ ] charArray = s. toCharArray ( ) ;
// 递推开始
// 先枚举子串长度
for ( int L = 2 ; L <= len; L ++ ) {
// 枚举左边界，左边界的上限设置可以宽松一些
for ( int i = 0 ; i < len; i++ ) {
// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
int j = L + i - 1 ;
// 如果右边界越界，就可以退出当前循环
if ( j >= len) {
break ;
}
if ( charArray[ i] != charArray[ j] ) {
dp[ i] [ j] = false ;
} else {
if ( j - i < 3 ) {
dp[ i] [ j] = true ;
} else {
dp[ i] [ j] = dp[ i + 1 ] [ j - 1 ] ;
}
}
// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if ( dp[ i] [ j] && j - i + 1 > maxLen) {
maxLen = j - i + 1 ;
begin = i;
}
}
}
return s. substring ( begin, begin + maxLen) ;
}
}
执行结果
复杂度分析
时间复杂度： O(n^2)
思路与算法 所有的状态在转移的时候的可能性都是唯一的 。也就是说，我们可以从每一种边界情况开始「扩展」，也可以得出所有的状态对应的答案。
边界情况即为子串长度为 11 或 22 的情况。我们枚举每一种边界情况，并从对应的子串开始不断地向两边扩展。如果两边的字母相同，我们就可以继续扩展，例如从 P(i+1,j-1)P(i+1,j−1) 扩展到 P(i,j)P(i,j)；如果两边的字母不同，我们就可以停止扩展，因为在这之后的子串都不能是回文串了。
聪明的读者此时应该可以发现，「边界情况」对应的子串实际上就是我们「扩展」出的回文串的「回文中心」。方法二的本质即为：我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案。
class Solution {
public String longestPalindrome ( String s) {
if ( s == null || s. length ( ) < 1 ) {
return "" ;
}
int start = 0 , end = 0 ;
for ( int i = 0 ; i < s. length ( ) ; i++ ) {
int len1 = expandAroundCenter ( s, i, i) ;
int len2 = expandAroundCenter ( s, i, i + 1 ) ;
int len = Math . max ( len1, len2) ;
if ( len > end - start) {
start = i - ( len - 1 ) / 2 ;
end = i + len / 2 ;
}
}
return s. substring ( start, end + 1 ) ;
}
public int expandAroundCenter ( String s, int left, int right) {
while ( left >= 0 && right < s. length ( ) && s. charAt ( left) == s. charAt ( right) ) {
-- left;
++ right;
}
return right - left - 1 ;
}
}
执行结果
复杂度分析
时间复杂度： O(n^2)
今天是力扣算法题打卡的第五天！今天的题有点难，借助力扣大神题解看了半天！ 文章采用 C# 和 Java 两种编程语言进行解题 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们 那今天的算法题分享到此结束啦，明天再见！
