005.md

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.

example:
Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

exmaple:
Input: "cbbd"

Output: "bb"

思路：

1

//运行较慢 ：动态规划。令len = s.size() 创建一个二维数组e[len][len]。e[i][j]存放下标为i到j所表示的子字符串的最大回文序列(e可以为string，也可以是pair 里边存放 两个下标表示子串)。
初始化e[i][j] 当i==j的情况，子串即为s[i];从子串长度l=2开始循环直到l长度为len。i为子串起始位置，j为子串末尾位置。
如果s[i] == s[j] 且i+1>j-1 表示 s[i]和s[j]是相邻的字符，则 e[i][j] = s[i] + s[j] 如果s[i] == s[j] 且i+1<=j-1 且 e[i][j].size() = j-i+1 表示 s[i]和s[j]不是相邻的字符，且中间整个子串都是最大回文序列，则 e[i][j] = s[i] + e[i][j] + s[j] 否则 e[i][j] = max(e[i+1][j],e[i][j-1]) //按题意，当e[i+1][j]==e[i][j-1] 优先等于e[i][j-1]. 返回e[1][len]。

2

情况1：字符串为空，返回空。
情况2，字符串的长度为1，返回s。
 情况3: 每一个点都有可能是回文子串的中间字符，所以用下标i 以每个字符为中间字符向两边检测。
  一个回文子串的中间字符可以能是一个字符或者一串相同的字符如：aaaaa。下标j，k初始化等于i,分别表示中间字符串的第一个字符和最后一个字符， 如果中间字符串长度1，则j==k。又有k-j+1表示中间字符串的长度。得到i，j表示中间字符串为：while ( s[k]==s[k+1] ) k++; 所以i是没必要等于后面a的索 引，因为第一个a检测出来的中间字符串的长度是最大的，而之后的a检测出来的中间字符串 就肯定是它所表示的回文了，因为j的前一个字符肯定是a 而k的后一个 字符肯定不是a ，所以可以更新更新i=k+1。
   得到中间字符串后，循环s[j-1]==s[k+1]检测是否构成回文，注意进入循环时j大于字符串起始位置(等于s[j-1]会向后溢出)，k小于字符串最后一个字符的索引(等于s[k+1]会溢出)，构成回文则j--，k++循环。以该中间字符串构成的最长回文子序列的长度即为temp_len = k-j+1如果temp_len>max_len则保存起始位置 max_index = j和当前最大长度temp_len，max_len为目前监测出来的最大长度，初始化为1，起始位置初始化为第一个字符的索引。
   优化：由于以i为中心字符开始监测的回文最长长度为 (s.size()-i) * 2 ，所以当(s.size()-i) * 2 < max_len即可退出循环。

代码：

1

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        s = " " + s;//0下标不用
        //二维数组e[i][j] 存放i到j所表示子字符串的最大回文序列的起始和末尾索引 
        vector<vector<pair<short,short>>> e;
        //为二维数组分配空间
        e.resize(len+1);
        for(int i=0;i<len+1;++i){
            e[i].resize(len+1);
        }
        //初始化i==j的情况
        for(int i=1;i<=len;++i){
            e[i][i].first = i;
            e[i][i].second = i;
        }
        //l为s的subtring的长度，从2开始到len。
        for(int l=2;l<=len;++l){
             //i为子串的起始索引
            for(int i=1;i<=len-l+1;++i){
                int j = i+l-1;//子串的末尾索引
                if(s[i]==s[j]){
                    int temp_sz;
                    if(i+1>j-1) temp_sz = 0;//说明s[i]和s[j]是相邻的字符
                    else temp_sz = e[i+1][j-1].second-e[i+1][j-1].first+1;
                    //i和j中间整个子串都是回文
                    if(temp_sz==l-2) {
                        e[i][j].first = i;
                        e[i][j].second = j;
                        continue;
                    }
                }
                 //否则等于e[i+1][j] 和 e[i][j-1]的较大者(长度)
                if((e[i+1][j].second-e[i+1][j].first+1) > (e[i][j-1].second-e[i][j-1].first+1)){
                    e[i][j] = e[i+1][j];
                }
                else{
                    e[i][j] = e[i][j-1];//优先取前面部分
                }
            }
        }

        string re = s.substr(e[1][len].first,e[1][len].second-e[1][len].first+1);
        return re;

    }
};

2

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.empty()) return "";
        if(s.size()==1) return s;
        s = " " + s;
        int max_index = 1,max_length = 1;
        int sz = s.size();
        for(int i=1;i<sz;  ){
            if( (sz-i)*2 < max_length) break;
            int j = i,k = i;//j表示中间字符串的其起始位置，k表示中间字符串的最后一个字符位置
            //检测出中间字符串(每一个字符相同)
            while(s[k]==s[k+1]){
                ++k;
            }
            //更新i ，第二个开始后的相同字符检测出来的回文肯定比第一个短，跳过检测
            i = k + 1;
            //向两边检测
            while(j>1 && k<sz-1 && s[k+1]==s[j-1] ){
                j--;
                k++;
            }
            int temp_len = k - j + 1;
            //更新最长回文长度和起始索引
            if(temp_len>max_length){
                max_index = j;
                max_length = k - j + 1;
            }
           // cout << max_index << " " << max_length<<endl;
        }
        return s.substr(max_index,max_length);
    }
};