Leetcode 5. Longest Palindromic Substring 题解

Last Updated At: 2016-03-31

题目链接

我的解

枚举回文字符串的中间位置,向两侧拓展。分偶数和奇数两种情况。

84ms

class Solution {
    public:
        std::string longestPalindrome(std::string s) {
            if (s.size()==0)
                return s;
            size_t max_len = 0;
            std::pair<size_t, size_t> res_ij;
            for (size_t i = 0; i < s.size(); ++i)
            {
                // odd case
                for (size_t j = 1; j <= i && i + j < s.size(); ++j)
                {
                    if (s[i - j] == s[i + j])
                    {
                        if (2 * j + 1 > max_len)
                        {
                            max_len = 2 * j + 1;
                            res_ij = std::make_pair(i, j);
                        }
                    }
                    else
                    {
                        break;
                    }
                }

                // even case
                for (size_t j = 1; j <= i && i + j -1 < s.size(); ++j)
                {
                    if (s[i - j] == s[i + j -1])
                    {
                        if (2 * j > max_len)
                        {
                            max_len = 2 * j;
                            res_ij = std::make_pair(i, j);
                        }
                    }
                    else
                    {
                        break;
                    }
                }
            }
            return max_len != 0 ? s.substr(res_ij.first - res_ij.second, max_len):s.substr(0, 1);
        }
};

更好的解

最长回文字符串有多种解法,可参考 Leetcode 上关于这个问题的两篇文章:

  1. Longest Palindromic Substring Part I
  2. Longest Palindromic Substring Part II

总结了暴力法、动态规划法、中心点法、Manacher法,其中暴力法时间复杂度,动态规划法和中心点法时间复杂度,Manacher算法可以将时间复杂度降低到

启发

看了Manacher算法,我当场念了一句:技不如人,甘拜下风!当我了解到还有时间复杂度 后缀树(Suffix tree) 时。。。Whatever,引用一句话:

This algorithm is definitely non-trivial and you won’t be expected to come up with such algorithm during an interview setting. However, I do hope that you enjoy reading this article and hopefully it helps you in understanding this interesting algorithm. You deserve a pat if you have gone this far! :)