5 Longest Palindromic Substring

Medium

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1 2	Input: "cbbd" Output: "bb"

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

1
2
3

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1 2	输入: "cbbd" 输出: "bb"

想法

这道题……想了一段时间，感觉最近做题速度好慢。实际上就是遍历每一个字符判断$s[i -j] == s[i+j]$和$s[i-j]==s[i+j+1]$也就是中间有一个字符和中间没有字符这两种情况是否成立。WA了一次，因为忘记在不成立的时候break掉了……

不过这个算法的复杂度是$O(n^2)$，有一个很有意思的算法Manacher‘s Algorithm复杂度是$O(n)$也就是线性复杂度，准备有时间好好看一下……

https://www.cnblogs.com/grandyang/p/4475985.html

https://www.cnblogs.com/schaepher/p/6543605.html

https://www.zhihu.com/question/37289584

https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/

解

class Solution {
  public:
    string longestPalindrome(string s)
    {
        int l = 0, max = 0;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= min(i, n - 1 - i); j++) {
                if (s[i - j] == s[i + j]) {
                    if (max < 2 * j + 1) {
                        l = i - j;
                        max = 2 * j + 1;
                    }
                }
                else
                    break;
            }
            for (int j = 0; j <= min(i, n - 2 - i); j++) {
                if (s[i - j] == s[i + j + 1]) {
                    if (max < 2 * (j + 1)) {
                        l = i - j;
                        max = 2 * (j + 1);
                    }
                }
                else
                    break;
            }
        }
        return string(s, l, max);
    }
};

2018-08-15

在Ubuntu Server上配置CUDA环境

Basic

5 Longest Palindromic Substring

想法

解

喜欢这篇文章？打赏一下作者吧

评论

链接

标签云

最新文章

归档

分类

标签

Your browser is out-of-date!