LeetCode 5. 最长回文子串(C++)

题目地址：力扣

寻找最长回文子串，意味着这样的子串是镜像的。我们可以发现，回文子串有这样的特点，要么是奇数个，比如aba；要么是偶数个，比如abba。奇数个则对中间元素是什么没有限制，只要左右两边对称就行；偶数个则没有中心元素，要求两边互相对称。

解法1：中心扩展搜索

对于每个字符，都可能是单中心或者双中心，因此在遍历的时候我们需要考虑单中心（回文子串长度为奇）和双中心（回文子串长度为偶数）两种情况，取两种情况的最大者作为我们最终的结果。代码如下：

注意：这种方法比较容易想到，但是实现起来的时候可以优化的地方要注意，第一个地方就是函数调用的时候传字符串的引用而不是复制，第二个地方就是遍历字符串的时候注意终止条件可以优化。

class Solution {
public:
    // 从中心向两边查找算法，注意这里s是const引用类型，若不引用，则会复制s造成内存占用高
    int expandFromCenter(const string &s, int left, int right)
    {
        // 只要左右不越界并且两边字符相等，就继续往左右找
        while (left >= 0 && right <= s.size() && s[left] == s[right])
        {
            --left, ++right;
        }
        // 返回当前找到的回文字符串的最大长度
        return right-left-1;
    }
 
    string longestPalindrome(string s) {
        // 初始化字符串长度，最大子串起始位置和最大子串长度
        int sz = s.size();
        int max_start = 0;
        int max_len = 1;
 
        // 遍历字符串，注意不需要遍历到最后一个元素，只需遍历到sz - (max_len/2)-1即可
        // 因为再往后就算后面都是回文，也不会超过最大长度了
        for(int i = 0; i < sz - (max_len/2); ++i)
        {
            // 单中心搜索
            int single_c = expandFromCenter(s, i-1, i+1);
            // 双中心搜索
            int double_c = expandFromCenter(s, i, i+1);
            // 取二者结果的最大值
            int cur_len = max(single_c, double_c);
            // 若结果比全局结果更大，就更新最大子串长度和起始位置
            if (cur_len > max_len)
            {
                max_len = cur_len;
                max_start = i;
            }
        }
    // 返回最长子串
    return s.substr(max_start-(max_len-1)/2, max_len);
    }
};

解法2：动态规划

思路：一个字符串是否是回文串，可以分解为更小规模的问题，比如一个字符串str = "abba" 是否为回文串，首先我可以判断str[0] == str[3]，也就是最左边和最右边做判断。若为真，我再判断字符串"bb"是否是回文串。若为假，我就不需要再继续进行判断，当前字符串必然不是回文串。因此当前字符串是否为回文串取决于两件事，第一件就是最左和最右的字符是否相等，第二就是其子串是否是回文串，因此我们可以利用子串的状态来转移到当前的状态。

我们再注意一下初始状态的设置，若要判断的字符串长度为1，那必然是回文串；若长度为2和3，只需要最左和最右的字符是否相等。因此我们可以得出，长度为2和3都可以从长度为1的状态得到，而长度为1的回文串属性是恒为真的。

class Solution {
public:
    string longestPalindrome(string s) {
        // sz代表字符串长度，剩下变量分别用于记录最长回文子串起始点以及最大长度
        int sz = s.size();
        int max_start = 0;
        int max_len = 1;
        // 开一个行和列长度都为sz的bool类型的二维数组，记录子串是否满足回文
        vectorbool>> dp(sz, vector<bool> (sz));
        // 从第字符串二个位置开始，从头往后找到这个位置，判断路径上的串是否回文
        for(int j = 1; j < sz; ++j)
        {
            for (int i = 0; i < j; ++i)
            {
                // 若发现最左和最右满足回文条件
                if (s[i] == s[j])
                {
                    // 若其长度等于2或者3，则直接判定为回文串，令其为true
                    if (j-i == 1 || j-i == 2)
                        dp[i][j] = true;
                    else
                    {   // 若长度大于3，则看看除开左右两头的，中间子串是否为回文
                        if (dp[i+1][j-1] == false)
                            continue;
                        // 子串为回文，则当前串也为回文，令其为true
                        dp[i][j] = true;
                    }
                    // 若当前串为回文，而且长度大于最大长度，则更新起点与及长度
                    if (dp[i][j] == true && (j-i+1) > max_len)
                    {
                        max_len = j-i+1;
                        max_start = i;
                    }
                }
            }
        }
        return s.substr(max_start, max_len);
    }
};

此外，我们注意到dp数组中，若行号为i，列号j必然大于i，因为我们是固定j，然后i从0开始前往后找的。因此我们并不需要给每一行都开sz大小的空间，我们只需要给每一行开sz-i的空间即可。例如字符串总长为4，若我们的从第二行看（i=1），其子串只可能为str[1][2], str[1][3], str[1][4]，即只需要3个空间来记录。因此我们可以对其进行空间优化，优化后的代码如下：

class Solution {
public:
    string longestPalindrome(string s) {
        int sz = s.size();
        int max_start = 0;
        int max_len = 1;
        vectorbool>> dp(sz);
        // 对于第i行分配只需要分配sz-i的空间
        for (int i = 0; i < sz; ++i)
        {
            dp[i] = vector<bool> (sz-i);
        }
        for(int j = 1; j < sz; ++j)
        {
            for (int i = 0; i < j; ++i)
            {
                if (s[i] == s[j])
                {
                    // 由于i行分配sz-i的空间，因此原本是j列的实际存储位置为j-(i+1)列
                    if (j-i == 1 || j-i == 2)
                        dp[i][j-(i+1)] = true;
                    else
                    {
                        if (dp[i+1][j-(i+1+1)-1] == false)
                            continue;
                        dp[i][j-(i+1)] = true;
                    }
                    if (dp[i][j-(i+1)] == true && (j-i+1) > max_len)
                    {
                        max_len = j-i+1;
                        max_start = i;
                    }
                }
            }
        }
        return s.substr(max_start, max_len);
    }
};

解法3：Manacher 算法

这个方法之后再更新

Accepted

• 140/140 cases passed (8 ms)
• Your runtime beats 97.4 % of cpp submissions
• Your memory usage beats 97.33 % of cpp submissions (6.6 MB)