Leetcode算法系列| 5. 最长回文子串

发布时间:2023年12月25日

1.题目

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

  • 示例1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
  • 示例 2:
输入:s = "cbbd"
输出:"bb"
  • 提示:
    • 1 <= s.length <= 1000
    • s 仅由数字和英文字母组成

2.题解

  • 首先我们会想到使用 暴力法 来解决题目,用3层循环来对每个子串进行检查,最后取最长的子串作为结果,这样时间复杂度为 O(n^3) 。然后可能会考虑到使用动态规划的方式,以空间来换取时间,可以将时间复杂度优化为 O(n^2),但相应的空间复杂度会增大。在仔细分析 回文串 的特点后,会想到使用 中心扩展法 ,该方法对于该题目来说不失为一种优秀的解决方法,时间复杂度为 O(n^2),空间复杂度为 O(1) ; 最后,还介绍了马拉车算法 Manacher ,这是一种非同寻常的算法,充分利用了 回文 的特点, 不可思议的将时间复杂度降为了 O(n) .

C# 解法一:暴力法

  • 使用 3层循环 来依次对所有子串进行检查,将最长的子串最为最终结果返回。下面代码中,我们检查i到j的子串是否是回文串,如果是 且长度大于当前结果result的长度,就将result更新为i到j的子串。
public class Solution {
      public string LongestPalindrome(string s)
    {
        string result = "";
        int n = s.Length;
        for (int i = 0; i < n; i++)
        {
            for (int j = i; j < n; j++)
            {
                // 检查 s[i]到s[j]是否是回文串,如果是,且长度大于result长度,就更新它
                int p = i, q = j;
                bool isPalindromic = true;
                while (p < q)
                {
                    if (s[p++] != s[q--])
                    {
                        isPalindromic = false;
                        break;
                    }
                }
                if (isPalindromic)
                {
                    int len = j - i + 1;
                    if (len > result.Length)
                    {
                        result = s.Substring(i, len);
                    }
                }

            }
        }
        return result;
    }
}

1

  • 时间复杂度:O(n^3)
    • 3层循环,所以是 O(n^3) .
  • 空间复杂度:O(1)
    • 仅使用了几个变量来存值,所以为 O(1) .

C# 解法二:动态规划

  • 方法一中,存在大量的重复计算工作,例如当 s=“abcba” 时, 对于子串 “bcb” 和 子串 “abcba”, 分别进行了2次完整的计算,来检测该子串是否是回文串。
    很明显的是,对于 s=“abcba” , 在已知 "bcb"是回文串的情况下,要判断 "bcb"是否是回文串的话,只需要判断两边的*位置的字符是否相等即可。 我们定义 P(i,j) 表示 s[i,j]是否是回文串,若s[i,j]是回文串,则P(i,j)=true,否则为false. 则有下面的递推公式成立:
P[i,j] =  p(i+1,j-1) && ( s[i]==s[j] ) 
  • 对于上面公式有2个特殊情况,当子串长度为1或2时,上面公式不成立。我们单独分析这两种情况:
若子串长度为1,即 j==i, 则 P[i,j] = P[i,i] = true; 
若子串长为2,即j==i+1, 则 P[i,j] = P[i,i+1] =  ( s[i]==s[i+1] )
  • 在实际执行时,我们先求所有长度为1的子串的P值,再求所有长度为2的子串的P值,之后再求长度3的,以此类推,一直到长度为s.Length的
public class Solution {
       public string LongestPalindrome(string s)
    {
        int n = s.Length;
        bool[,] P = new bool[n, n];
        string result = "";
        //遍历所有的长度
        for (int len = 1; len <= n; len++)
        {
            for (int start = 0; start < n; start++)
            {
                int end = start + len - 1;
                if (end >= n) //下标已经越界,结束本次循环
                    break;
                //长度为 1 和 2 的单独判断下
                P[start, end] = (len == 1 || len == 2 || P[start + 1, end - 1]) && s[start] == s[end];
                if (P[start, end] && len > result.Length)
                {
                    result = s.Substring(start, len);
                }
            }
        }
        return result;
    }
}

2

  • 时间复杂度:O(n^2)
    • 两层循环,所以是 O(n^2)
  • 空间复杂度:O(n^2)
    • P是二维数组,所以是 O(n^2)

C# 解法三:中心扩展法

  • 对于回文串,我们可以找到一个中心,从这个中心向两边扩展的话,两边对应的值是相等的。按照这个逻辑,我们只需要一层主循环 i 将 s 遍历一遍即可,并在循环内部 将s[i]视为中心 使用中心扩展法来求出以s[i]为中心的最长的回文串;当i将s遍历完后,即可得到s的最长回文串。
    下面我们以 s=“abcbc”, 且 i==2 为例,讨论一下如何进行中心扩展。
  1. i==2指向c,我们初始化两个指针p与q都指向这个c
  2. p–,q++,p指向了左边b,q指向了右边b
  3. 因为s[p]==s[q], 所以再次执行p–,q++,此时p指向了最左边a,q指向了最右边c
  4. 因为s[p]!=s[q],所以结束扩展。
public class Solution {
   public string LongestPalindrome(string s)
   {
       string result = "";
       int n = s.Length;
       int end = 2 * n - 1;
       for (int i = 0; i < end; i ++)
       {
           double mid = i / 2.0;
           int p = (int)(Math.Floor(mid));
           int q = (int)(Math.Ceiling(mid));
           while (p >= 0 && q < n)
           {
               if (s[p] != s[q]) break;
               p--; q++;
           }
           int len = q - p - 1;
           if (len > result.Length)
               result = s.Substring(p + 1, len);
       }
       return result;
   }
}

3

  • 时间复杂度:O(n^2)
    • 主循环执行约2n次,内部while最多执行约n/2次(从s最中心向外扩展到s头和s尾),所以复杂度为 O(n^2).
  • 空间复杂度:O(1)
    • 仅使用了几个变量来存值,所以空间复杂度为O(1)

C# 解法四:马拉车算法

  • 马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性方法,由一个叫 Manacher 的人在 1975 年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性。
    首先我们需要解决s长度可能为奇数或偶数的问题。在每个字符间插入 “#”,经过处理,字符串的长度永远都是奇数了
public class Solution {
       public string PreProcess(string s)
   {
       string t = "^";
       int n = s.Length;
       if (n == 0) return "^$";
       for (int i = 0; i < n; i++)
       {
           t += "#" + s[i];
       }
       t += "#$";
       return t;
   }

   // 方法四:马拉车算法 108ms,26.4M
   public string LongestPalindrome(string s)
   {
       string t = PreProcess(s);
       int n = t.Length;
       int[] p = new int[n];
       int c = 0, r = 0;
       //计算P
       for (int i = 1; i < n - 1; i++)
       {
           int j = 2 * c - i;
           //情况2和3可以总结为 p[i]= min(r - i + 1, p[j]) ,情况1为 p[i]=1;
           p[i] = r > i ? Math.Min(r - i + 1, p[j]) : 1;
           //对于情况4和1,直接扩展即可;
           //对于情况2和3,也可以直接扩展;虽然一定扩展不了,但是这样的计算过程比“判断是情况2或3”的计算量还要小,仔细品味
           while (t[i - p[i]] == t[i + p[i]])
           {
               p[i]++;
           }
           if (i + p[i] > r)
           {
               //找到了更长的回文串,更新c和r
               c = i;
               r = i + p[i] - 1;
           }
       }
       // 找出 P 的最大值
       int maxLen = 0;
       int centerIndex = 0;
       for (int i = 1; i < n - 1; i++)
       {
           int len = p[i] - 1;
           if (len > maxLen)
           {
               maxLen = len;
               centerIndex = i;
           }
       }
       int start = (centerIndex - maxLen) / 2;
       return s.Substring(start, maxLen);
   }
}

4

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
    • 因为p数组空间复杂度为 O(n).
文章来源:https://blog.csdn.net/backlighting2015/article/details/135173996
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。