LeetCode 第五题 最长的回文字符串 (JAVA)

时间:2024-09-12 16:07:08

Longest Palindromic Substring

简介:字符串中最长的回文字符串

回文字符串:中心对称的字符串 ,如 mom,noon

问题详解:

给定一个字符串s,寻找字符串中最长的回文字符串,假设字符串s长度最长为1000.

举例:

1:

输入: “babad”

输出: “bab”

注: “aba” 也是一种答案.

2:

输入: “cbbd”

输出: “bb”

官方实现 : Expand Around Center

我们可以从字符串中心寻找回文字符串,例如"aba"的中心为’b’,"baab"的中心为两个a中间,所以分两种情况考虑,一种是中心为i,另一种是i和i+1,这里我们需要注意的是String里的方法substring(index start,index end),第二个s是小写的,并且是从start开始一直到end结尾但不包含end索引处的字符,所以我们要end+1

LeetCode 第五题 最长的回文字符串 (JAVA)

复杂度分析

时间复杂度分析 : O(n^2).

空间复杂度 : O(1).

小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海