[leetcode] 5. Longest Palindromic Substring

[leetcode] 5. Longest Palindromic Substring

Description

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

Example 1:

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

Example 2:

Input: "cbbd"Output: "bb"

分析

题目的意思是：找出一个字符串中的最长回文子串。

这道题从中间开花，遍历每个结点，把每个节点都当作回文子串的中心位置，然后向左右拓展，找出所有这种回文子串中最长的就够了。

代码

class Solution {public: string longestPalindrome(string s) { int max_len=0; int start=0; for(int i=0;i=0&&rightmax_len){ max_len=cur_len; start=left; } left--; right++; } left=i; right=i+1; while(left>=0&&right<=s.length()&&s[left]==s[right]){ int cur_len=right-left; if(cur_len>max_len){ max_len=cur_len; start=left; } left--; right++; } } return s.substr(start,max_len+1); }};

参考文献

​​Manacher’s Algorithm 马拉车算法​​​​LeetCode 5. Longest Palindromic Substring（最长回文连续子串）​​​​[Leetcode] Longest palindromic substring 最长回文子串​​​​Longest Palindromic Substring Part II​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。