题目

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

Example:

1
2
3
4
5
Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

1
2
3
Input: "cbbd"

Output: "bb"

大意

找出最长的回文字符串

答案（神坑。。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int extend(string s,int j,int k)
    {
        while(s[j]==s[k]&&j>=0&&k<s.size())
        {
            j--;
            k++;
        }
        return k-j-1;
    }// 给出中间数，向两边扩展，找到最长的不等边界。
    string longestPalindrome(string s)
    {
        int len = s.size();
        int start = 0;
        int end = 0;    
        int leng =0;
        int maxlen =0;
        for(int i=0;i<len;i++)
        {
            int len1 = extend(s,i,i); //aba型的最大值 
            int len2 = extend(s,i,i+1);//abba型的最大值
            int leng = max(len1,len2);// 相比较的最大值。
            if(leng>maxlen)
            {
                maxlen =leng;
                start = i-(maxlen-1)/2; 
                end = start+leng-1;
            }
        }
        return s.substr(start,maxlen);//神坑在此，Java中subString的参数是左坐标，右坐标的下一位，然而c++中的substr第一个参数为开始，第二个参数是截取的个数。。。简直rlg。
    } 
};

思路

直接从中间开始寻找，直至找到最远的边缘。
回数的中间可能是一个单值，如aba中的b；也可能是双值，如abba中的bb。
我们可以对当前下标上的单值双值都进行尝试。