首页 > 代码库 > LeetCode --- 5. Longest Palindromic Substring

LeetCode --- 5. Longest Palindromic Substring

2024-11-19 15:17:02   202人阅读

题目链接：Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

这道题的要求是在字符串中找出最长回文子串。假设字符串长度小于等于1000，而且最长回文子串唯一。

1. 暴力查找

对每个子串判断是否是回文，遍历每个子串需要两层循环，时间复杂度O(n2)，判断回文时间复杂度是O(n)。这里就不上代码了。。。

时间复杂度：O(n3)

空间复杂度：O(1)

2. 遍历中心点

由于回文是左右对称的，因此可以遍历字符串选定中心点，然后向两边扫描直到不是回文为止。总共有2n-1个（n个中心点是字符，n-1个中心点是2个相邻字符间隙）中心点，对于每个中心点向两边扫描时时间复杂度O(n)。

时间复杂度：O(n2)

空间复杂度：O(1)

 1 class Solution
 2 {
 3 private:
 4     int palindrome(string s, int b, int e)
 5     {
 6         while(b >= 0 && e < s.size() && s[b] == s[e])
 7             --b, ++e;
 8         return e - b - 1;
 9     }
10 
11 public:
12     string longestPalindrome(string s)
13     {
14         int b, l = 0;
15         for(int i = 0; i < s.size(); ++i)
16         {
17             int len = max(palindrome(s, i, i), palindrome(s, i, i + 1));
18             if(len > l)
19             {
20                 b = i - (len - 1) / 2;
21                 l = len;
22             }
23         }
24         
25         return s.substr(b, l);
26     }
27 };

3. Manacher算法

Manacher算法是针对寻找最长回文子串的线性算法。

这里不详细介绍了，想要了解的看这里

时间复杂度：O(n)

空间复杂度：O(1)

转载请说明出处：LeetCode --- 5. Longest Palindromic Substring

LeetCode --- 5. Longest Palindromic Substring


联系
我们