【Leetcode】最长回文子串

启发

1）做题前一定要读懂题目

在本题中，首先要清楚地定义回文子串的概念，然后才能设计算法查找它。

如中心扩散法，其主要思想在于找到一个回文子串的定义——两侧互为镜像。进一步分为奇数长度和偶数长度进行讨论。

在这里附上kaggle宗师高志峰的心得，

2）查找的过程要非常注意边界的处理

这往往是非常容易放错的地方！

中心扩散法

我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n−1 个这样的中心。

你可能会问，为什么会是 2n−1 个，而不是 n 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如“abba” 的中心在两个‘b’ 之间）。

时间复杂度 O(n^2), 由于围绕中心来扩展回文会耗去 O(n) 的时间，所以总的复杂度为 O(n^2);

空间复杂度 O(1);

执行用时 : 128 ms, 在Longest Palindromic Substring的C++提交中击败了54.24% 的用户

内存消耗 : 104 MB, 在Longest Palindromic Substring的C++提交中击败了26.33% 的用户

class Solution {

public:

    string longestPalindrome(string s) {

        if (s == "" || s.size()== )

        {

            return s;

        }

        int size = s.size();

        int start = ;

        int max = ;

        int len1 = , len2 = ;

        int len = ;

        for (int i = ; i < size; i++)

        {

            len1 = retRomeLen(s, i, i);

            len2 = retRomeLen(s, i, i + );

            len = len1>len2 ? len1 : len2;

            if (len > max)

            {

                max = len;

                start = i - (len-) / ;

            }

        }

        return s.substr(start, max);

    }

    // 中心扩散的宽度

    int retRomeLen(string s, int left, int right)

    {

        while (left >=  && right < s.size() && s[left] == s[right] )

        {

            left--;

            right++;

        }return right - left -;

    }

};

把上述代码中查找回文的函数改成如下，

int retRomeLen(string& s, int left, int right)

结果大幅度提升，

执行用时 : 24 ms, 在Longest Palindromic Substring的C++提交中击败了85.89% 的用户

内存消耗 : 8.6 MB, 在Longest Palindromic Substring的C++提交中击败了96.80% 的用户

动态规划

时间复杂度：O(n^2)。将长度为n的字符串从前往后划分为1,2,3……n-1，n的子串，在每个子串内寻找回文。前一个子串中的回文寻找结果将被后一个子串所使用。

空间复杂度：O(n^2)

执行用时 : 172 ms, 在Longest Palindromic Substring的C++提交中击败了46.34% 的用户

内存消耗 : 9.8 MB, 在Longest Palindromic Substring的C++提交中击败了66.80% 的用户

class Solution {

public:

    string longestPalindrome(string s) {

        int n=s.size();

        if(n==) return s;

        bool dp[n][n];

        memset(dp,,sizeof(dp));

        int maxlen=,start=;

        for(int i=;i<n;i++)

        {

            for(int j=;j<=i;j++)

            {

                if(i-j<) dp[i][j]=(s[i]==s[j]);

                else

                    dp[i][j]=(s[i]==s[j]&&dp[i-][j+]==);

                if(dp[i][j]&&maxlen<i-j+)

                {

                    maxlen=i-j+;

                    start=j;

                }

            }

        }

        return s.substr(start,maxlen);

    }

};

动态规划法解析：

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-bao-gu/

偶然穿插的代码优化：

中心扩散法的空间复杂度是 O(1)，远远优于动态规划法的 O(n^2)，然而内存消耗却是十倍。思考之后得到启发！中心扩散法中为使代码更为美观，将查找回文的功能封装成一个函数进行调用。在函数调用过程中，内存需要开辟一块栈空间，存储函数调用的各种信息。尽管函数执行过程中耗费的内存很小，几乎可以忽略，然而为了记录函数调用产生的数据，却占了大头。

将中心扩散法的代码改成如下形式，取消函数的调用，效果改变显著！

执行用时 : 36 ms, 在Longest Palindromic Substring的C++提交中击败了75.65% 的用户

内存消耗 : 8.9 MB, 在Longest Palindromic Substring的C++提交中击败了91.93% 的用户

class Solution {

public:

    string longestPalindrome(string s) {

        if (s == "" || s.size()== )

        {

            return s;

        }

        int size = s.size();

        int start = ;

        int max = ;

        int len1 = , len2 = ;

        int len = ;

        for (int i = ; i < size; i++)

        {

            int left = i, right = i;

            while (left >=  && right < s.size() && s[left] == s[right] )

            {

                left--;

                right++;

            }

            len1 = right - left -;

            left = i; right = i+;

            while (left >=  && right < s.size() && s[left] == s[right] )

            {

                left--;

                right++;

            }

            len2 = right - left -;

            len = len1>len2 ? len1 : len2;

            if (len > max)

            {

                max = len;

                start = i - (len-) / ;

            }

        }

        return s.substr(start, max);

    }

};

巴特西

【Leetcode】最长回文子串

最新文章

热门文章