使用LeetCode怎么求最长回文子串
这期内容当中小编将会给大家带来有关使用LeetCode怎么求最长回文子串,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。
目前创新互联已为近1000家的企业提供了网站建设、域名、网站空间、网站运营、企业网站设计、建湖网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。
描述
难度:中等
给你一个字符串 s,找到 s 中最长的回文子串。
示例 1:
输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd" 输出:"bb"
示例 3:
输入:s = "a" 输出:"a"
示例 4:
输入:s = "ac" 输出:"a"
提示:
1 <= s.length <= 1000 s 仅由数字和英文字母(大写和/或小写)组成
Solution
中心扩散法
解题思路
都是回文数,这次是最长的回文数,并且包含字符串和数字,所以跟之前第五题的
回文数
,完全是两个题,没有可借鉴的地方最终的结果是需要在字符串中找到最长的回文数,那么我们可以假定从字符串的
每个字符
开始,都有回文数
,通过遍历整体字符串的长度,并且算出每个字符回文数的长度,最后比较最长的数即可假定每个字符都是存在
回文数
的,那么只有两种情况,回文子串长度为奇数(如
aba
,中心是(b
))回文子串长度为偶数(如
abba
,中心是(b,b
)无论字符串
S
是奇数还是偶数,判断回文数从当前字符开始,M==N
,其中M
为中心的开始,N
为相邻的数字,奇数时,MN
为同一个字符,偶数时,MN
为M,N=(M+1)
,如果S[M]==S[N]
,则进行扩散,使M--
,N++
,继续判断S[M--],S[N++]
的值,相等则继续M--,N++
,直到S[M--],S[N++]
不相等或者超越边界(M<0 OR N > = S.length()
)为止
CODE
class Solution { public String longestPalindrome(String s) { int len = s.length(); String res = ""; //如果小于2,直接返回 if(len < 2){ return s; } for(int i =0;i=0 && (n < s.length()) && (s.charAt(m) == s.charAt(n))){ //扩散,对应-- m--; //扩散,对应++ n++; } //这里其实是(n-1)-(m+1)-1,在上面while之后,会m--以及n++,比实际位置偏差一位 if((n-m-1) > res.length()){ //截取m+1位置,到n-1的地方,上面while比实际位置偏差一位,所以m需要+1,n不需要-1 res=s.substring(m+1,n); } return res; } }
复杂度
时间复杂度:
O(N2)
,N
为字符串长度,每个字符串向外遍历最多可能N
个空间复杂度:
O(1)
结果
执行用时:
37
ms, 在所有Java
提交中击败了76.50
%的用户内存消耗:
39
MB, 在所有Java
提交中击败了58.36
%的用户
上述就是小编为大家分享的使用LeetCode怎么求最长回文子串了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注创新互联行业资讯频道。
网站栏目:使用LeetCode怎么求最长回文子串
文章地址:http://ybzwz.com/article/ggiieo.html