不会飞的章鱼

熟能生巧，勤能补拙；念念不忘，必有回响。

LintCode-200-Longest Palindromic Substring | 最长回文子串

发表于 更新于 分类于
本文字数： 981 阅读时长 ≈ 1 分钟

题目

lintcode

暴力循环O(n^3)

1
2
3
4
5
6
伪代码
for 起点 O(n)
    for 终点 O(n)
        检测中间的子串是不是一个回文串 O(n)

时间复杂度：O(n^3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#python3
class Solution:
    """
    @param s: input string
    @return: a string as the longest palindromic substring
    """
    def longestPalindrome(self, s):
        # write your code here
        for length in range(len(s),0,-1):
            for i in range(len(s) - length + 1):
                l,r = i,i+length-1
                while l < r and s[l] == s[r]:
                    l+=1
                    r-=1
                if l>=r:
                    return s[i:i+length]
        return ""

O(n^3) 的实现方法下比较好的Coding Quality

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    """
    @param s: input string
    @return: a string as the longest palindromic substring
    """
    def longestPalindrome(self, s):
        if s is None:
            return None
        
        for length in range(len(s),0,-1):
            for i in range(len(s) - length + 1):
                if self.is_palindrome(s, i, i + length - 1):
                    return s[i:i + length]

        return ""

    def is_palindrome(self,s,left,right):
        while left < right and s[left] == s[right]:
            left += 1
            right -= 1
        
        return left >= right

(待更新)

基于中心点枚举法 Enumeration的最佳实践

基于中心线枚举的方法

基于动态规划 Dynamic Programming 的最佳实践

基于区间型动态规划的解法

------ 本文结束------
如果本篇文章对你有帮助，可以给作者加个鸡腿~(*^__^*)，感谢鼓励与支持！