5. Longest Palindromic Substring（最长回文串）

布满荆棘的人生 2022-12-02 10:49 112阅读 0赞

两个思路：**一个O（N^2), 一个O（N）时间复杂度**  
思路一：**n^2的是通过从每个节点往两边扩**  
思路二：manacher算法，通过先扩展字符串用\#隔开，然后遍历的过程中记录一个当前最大右边界，以当前i 为中心的回文串长度（因为加了\#字符，所以相当于就是可以用这个值得出回文串长度），因为是对称的所以很容易得到另外一边的对应那个char

思路1：  
manacher算法：  
首先加入\#分割字符串，因为这样可以单数偶数都计算进去。  
然后开始遍历。几个状态量：右边界，中心点， 长度数组，最大长度，开始的地方（需要返回字符串）

class Solution { 
    //更加一般性的：1 扩充字符串（适应偶数奇数；2 遍历同时数据改变
    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;
            int start = 0;
    
            for (int i = 0; i < strSize; ++i) { 
                if (i < maxRight) { 
                    p[i] = min(maxRight - i, p[2*center-i]);    //镜像到左边的回文子串的长度
                }
    
                int left = i - (1 + p[i]);      //这两个是（）开区间，因为马上要测试了
                int right = i + (1 + p[i]);     //因为一开始p[i]=0都是
    
                // 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) { 
                    // 记录最长回文子串的长度和相应它在原始字符串中的起点
                    maxLen = p[i];
                    start = (i - maxLen) / 2;       //最开始的地方
                }
            }
            return s.substr(start, maxLen);
        }
    
    };

思路2：  
code：为了区分单数回文和偶数回文，所以第一层遍历的时候，需要用i 和i+1两个计算.

#include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    class Solution { 
    
    private:
    
        string centerSpread(string s, int left, int right) { 
            // left = right 的时候，此时回文中心是一个空隙，向两边扩散得到的回文子串的长度是奇数
            // right = left + 1 的时候，此时回文中心是一个字符，向两边扩散得到的回文子串的长度是偶数
            int size = s.size();
            int i = left;
            int j = right;
            while (i >= 0 && j < size) { 
                if (s[i] == s[j]) { 
                    i--;
                    j++;
                } else { 
                    break;
                }
            }
            // 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j
            return s.substr(i + 1, j - i - 1);	//take care。
        }
    
    public:
    
    
        string longestPalindrome(string s) { 
            // 特判
            int size = s.size();
            if (size < 2) { 
                return s;
            }
    
            int maxLen = 1;
            string res = s.substr(0, 1);
    
            // 中心位置枚举到 len - 2 即可
            for (int i = 0; i < size - 1; i++) { 
                string oddStr = centerSpread(s, i, i);		//take care
                string evenStr = centerSpread(s, i, i + 1);
                string maxLenStr = oddStr.size() > evenStr.size() ? oddStr : evenStr;
                if (maxLenStr.length() > maxLen) { 
                    maxLen = maxLenStr.size();
                    res = maxLenStr;
                }
            }
            return res;
        }
    };