LeetCode：Longest Palindromic Substring

青旅半醒 2022-07-12 07:43 117阅读 0赞

第五题是求字符串里的最大回文子串，回文串（Palindromic Substring）就是例如”aba”，“abba”这种，网上有很多使用解决方法，比如使用动归，kmp的变种等解法，时间复杂度从O(n^3)甚至到O(n)。

我这里的结题思路是，对字符串里的每一个字符向两边展开，字符串长度增加的条件如下:

*  如果s\[end\] == s\[end+1\]，end++，长度加1
 *  如果s\[begin-1\] == s\[end +1\], begin–且end++，长度加2
 *  注意循环过程中end小于len(s)-1，begin大于0

代码如下：

#! /usr/bin/env python
        # -*- coding -*-
    
        class Solution(object):
            def longestPalindrome(self, s):
                """ :type s: str :rtype: str """
                length = len(s)
                max_len = 0
                index = 0
                if length == 0 or length == 1:
                    return s
                for i in range(0, length):
                    begin = i
                    end = i
                    while end < length - 1 and s[end] == s[end+1]:
                        end = end + 1
                    while end < length - 1 and begin > 0 and s[begin - 1] == s[end + 1]:
                        begin = begin - 1
                        end = end + 1
                    if max_len < end - begin + 1:
                        max_len = end - begin + 1
                        index = begin
    
                return s[index:index + max_len]
    
        if __name__ == "__main__":
            s = Solution();
            print s.longestPalindrome('aabcbcbaacbeeeeeeeeebc')

因为使用了两层循环，所以时间复杂度是O(n)，网上也有同学做到了复杂度为O(n)，我赶紧去膜拜学习一下。

发表评论取消回复

表情：

评论列表（有 0 条评论，117人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode Longest Palindromic Substring

题目 Given a string S, find the longest palindromic substring in S. You may assume that

本是古典何须时尚/ 2022年08月05日 00:51/ 0 赞/ 132 阅读

相关 5 Longest Palindromic Substring

Given a string S, find the longest palindromic(adj. 回文的；复发的) substring in S. You may ass

向右看齐/ 2022年08月01日 00:11/ 0 赞/ 5 阅读

相关 LeetCode：Longest Palindromic Substring

第五题是求字符串里的最大回文子串，回文串（Palindromic Substring）就是例如”aba”，“abba”这种，网上有很多使用解决方法，比如使用动归，kmp的变种等

青旅半醒/ 2022年07月12日 07:43/ 0 赞/ 118 阅读

相关 LeetCode：Longest Palindromic Substring

第五题是求字符串里的最大回文子串，回文串（Palindromic Substring）就是例如”aba”，“abba”这种，网上有很多使用解决方法，比如使用动归，kmp的变种等

谁践踏了优雅/ 2022年07月12日 07:43/ 0 赞/ 93 阅读

相关 Leetcode——5. Longest Palindromic Substring

1. 概述 Given a string s, find the longest palindromic substring in s. You may assume t

柔情只为你懂/ 2022年06月15日 07:21/ 0 赞/ 176 阅读

相关 LeetCode-Palindromic Substrings

文章目录 LeetCode-Palindromic Substrings 题目描述思路分析 C++实现 Sc

た入场券/ 2022年04月23日 10:22/ 0 赞/ 127 阅读

相关 LeetCode-Longest Palindromic Substring

文章目录 LeetCode-Longest Palindromic Substring 题目描述思路分析 C++实现

- 日理万妓/ 2022年03月20日 03:31/ 0 赞/ 127 阅读

相关 5. Longest Palindromic Substring

description: Given a string s, find the longest palindromic substring in s. You may a

旧城等待，/ 2021年12月24日 19:04/ 0 赞/ 209 阅读

相关 Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the m

青旅半醒/ 2021年12月17日 10:33/ 0 赞/ 184 阅读

相关 LeetCode 5. Longest Palindromic Substring

一、试题 Given a string s, find the longest palindromic substring in s. You may assume th

以你之姓@/ 2021年06月24日 15:57/ 0 赞/ 322 阅读