当前位置 : 主页 > 手机开发 > ROM >

Longest Palindromic Substring

来源:互联网 收集:自由互联 发布时间:2021-06-10
题目内容如下: Given a strings, find the longest palindromic substring ins. You may assume that the maximum length ofsis 1000. Example 1: Input: "babad"Output: "bab"Note: "aba" is also a valid answer. Example 2: Input: "cbbd"Output:

题目内容如下:

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 length=s.length();
       if(length<2)
           return s;
       int left=0,right=0,maxLength=0,startIndex=0,next=0;
    while(next<length){
        left=next;
        right=next;
        while(s[right]==s[right+1])right++;
        next++;
        while(left>0&&right<length-1&&s[left-1]==s[right+1]){
            left--;
            right++;
        }
        if(right-left+1>maxLength){
            startIndex=left;
            maxLength=right-left+1;
        }
    }
       return s.substr(startIndex,maxLength);
}
};

虽然是暴力解法,但当时看到其他人的方法还是花了一段时间才理解的。这里有两处需要注意的地方:

1.next指向的是下一个要分析的位置。在每次开始分析时,left和right都指向同一个位置,之后left向左,right向右,直到两处内容不相同为止

2.对于重复的段落要直接跳过分析,因为对于重复部分一定是回文的,不论奇偶,所以直接将他们包括在上一段回文序列的长度中即可(即对于有重复部分的序列,回文部分的长度一定大于等于重复部分的长度)

另外,对于在串中寻找最长回文子串的问题,有一种著名的马拉车算法,但是自己还没有看懂QAQ,先mark一下:

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

网友评论