Leetcode 5 最长回文子串

题目描述

给你一个字符串 s，找到 s 中最长的回文子串

题解1 (超时，但是结果没问题，先找思路再优化)

class Solution {
public:
    string longestPalindrome(string s) {
        string r_s = "";
        auto length = s.length();
        int l_maxx = -1;
        string maxx = "";
        for(int r = 1; r <= length; r++){
            for(int i = length-r; i >= 0; i--){
                r_s += s[i];
                //倒序是为了找这个位置，如果是和其他位置相同则不是所需
                if(s.find(r_s) == i){
                    if(l_maxx < (int)r_s.length()){
                        l_maxx = r_s.length();
                        maxx = r_s;
                    }
                }
            }
            r_s.clear();
        }
        return maxx;
    }
};

暴力果然只通过了不到1/3

题解2(DP)

class Solution {
public:
    string longestPalindrome(string s) {
        int s_len = s.length();
        int left = 0;
        //动态规划：填表dp
        //分析：根据回文串，对于两个下标建立起关系，能想到3个字符和2个字符都可以用两边的字符来判断是不是回文串；例如： aba 只需要判断 a=a,则这个串的长度就为3；例如：aa a=a则这个串的长度就为2；转换成下标就可以理解为dp[i][j]=true(是回文串)，记录下标即记录长度
        //所以在思考状态表达式时，递进关系就如下： 
        //当判断两边字符相等时，若j-i+1 <= 3 dp[i][j]=true
        //若j-i>=3 dp[i][j]=dp[i+1][j-1] (因为两边已经判断相等，所以相当于双指针靠拢继续判断)
        vector<vector<bool>> dp(s_len, vector<bool>(s_len, false));
        int maxx = 1;
        for(int i = 1; i < s_len; i++){
            for(int j = 0; j < i; j++){
                if(s[i] == s[j]){
                    if(i - j < 3)
                        dp[j][i] = true;
                    else 
                        dp[j][i] = dp[j+1][i-1];
                }
                if(dp[j][i] && i-j+1 > maxx){
                    maxx = i-j+1;
                    left = j;
                }
            }
        }
        return s.substr(left, maxx);
    }
};

题解3(中心扩散基础)

private:
    void takefirst_len(int& left, int& len, int i, int j, int t_len, string s){
         while(i >= 0 && j < t_len){
         //i是左指针 j是右指针
            if(s[i] == s[j]){
                if(j-i+1 > len){
                    left = i;
                    len = j-i+1;
                }
                i--;
                j++;
            }else{
                break;
            }
        }
        
    }
public:
    string longestPalindrome(string s) {
        auto length = s.length();
        int left = 0;
        int l_maxx = 1;
        for(int r = 0; r < length; r++){
        //r是中心
            takefirst_len(left, l_maxx, r, r, length, s);
            takefirst_len(left, l_maxx, r, r+1, length, s);
        }
        return s.substr(left, l_maxx);
    }

题解4(Manacher)(代码参考)

class Solution {
public:
    string longestPalindrome(string s) {
    // 特判
	int size = s.size();
    if (size < 2) {
        return s;
    }

    // 得到预处理字符串
    string str = "#";
    for (int i = 0; i < s.size(); ++i) {
        str += s[i];
        str += "#";
    }
    // 新字符串的长度
    int strSize = 2 * size + 1;
    // 数组 p 记录了扫描过的回文子串的信息
    vector<int> p(strSize, 0);

    // 双指针，它们是一一对应的，须同时更新
    int maxRight = 0;
    int center = 0;

    // 当前遍历的中心最大扩散步数，其值等于原始字符串的最长回文子串的长度
    int maxLen = 1;
    // 原始字符串的最长回文子串的起始位置，与 maxLen 必须同时更新
    int start = 0;
    for (int i = 0; i < strSize; ++i) {
         if (i < maxRight) {
             int mirror = (2 * center) - i;
             // 这一行代码是 Manacher 算法的关键所在，要结合图形来理解
             //mirror位置偏左，所以避免maxRight-i太大 越界
             p[i] = min(maxRight - i, p[mirror]);
        }

        // 下一次尝试扩散的左右起点，能扩散的步数直接加到 p[i] 中
        int left = i - (1 + p[i]);
        int right = i + (1 + p[i]);
         // left >= 0 && right < sLen 保证不越界
         // str.charAt(left) == str.charAt(right) 表示可以扩散 1 次
       while (left >= 0 && right < strSize && str[left] == str[right]) {
            p[i]++;
            left--;
            right++;

       }
       // 根据 maxRight 的定义，它是遍历过的 i 的 i + p[i] 的最大者
       // 如果 maxRight 的值越大，进入上面 i < maxRight 的判断的可能性就越大，这样就可以重复利用之前判断过的回文信息了
       if (i + p[i] > maxRight) {
           // maxRight 和 center 需要同时更新
           maxRight = i + p[i];
           center = i;
       }
       if (p[i] > maxLen) {
          // 记录最长回文子串的长度和相应它在原始字符串中的起点
          //注意拓展了s： #填充 --> 奇数个字符
           maxLen = p[i];
           start = (i - maxLen) / 2;
        }
    }
    return s.substr(start, maxLen);
  }
};   

马拉车得多看几遍喵喵喵