每日算法---5. 最长回文子串  中等   原题  

    今天又是快乐的一天,我们来分享一道动态规划的题目,不算很难。

题目:

    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例2:
输入: "cbbd"
输出: "bb"

解题:

   题意很简单,就是让我们找出一个串中的最大回文子串,然后返回

   我们最先能想到的就是暴力去扩散了吧,但是这样的解法我们的时间复杂度会达到(n^3),这样的当然是过了题的。而且这样,我们还会去纠结回文串时奇数个,还是偶数个。所以情况又变得复杂起来。

   所以这道题给大家讲解,两种算法,第一种是动态规划,第二种 中心扩散。总体来说,动态规划是没有第二种算法好的,但是动态规划是比较普遍的解题思路,而中心扩散却很难用于其他题目。所以我们首先讲动态规划。

题解1:动态规划

   其实动态规划说的高大上,绝大多数情况都是使用损失空间来换取时间,那接下来我们就说说,动态规划相对于暴力解法的优点在哪里。

   其实暴力解法呢,我们每次都去重新比对他是不是回文,但是在前n-1次时,我们比对的结果被我们所丢弃啦,就和昨天说的一样,这叫信息浪费(参见KMP算法详解),那么我们动态规划基本上就是将这一信息储存起来,用于判断下一次的比对,至于如何存储,每一题都会不同。

   于本题来说,我们将 l , r 之间是否为回文串进行记录,那我们可以想到,qp[l][r] = true;表示是回文串,那么我们在判断 l - 1 , r + 1 之间是否是回文的时候,我们是不是只需要判断 str[l - 1] == str[r + 1],所以我们就并不需要去从头开始遍历比对啦。

    每个动态规划题都可以找出一个动态转移方程,动态规划关键是找到初始状态和状态转移方程。

    (1)初始状态,l=r时,此时dp[l][r]=true。

    (2)状态转移方程,dp[l][r]=true并且(l-1)和(r+1)两个位置为相同的字符,此时dp[l-1][r+1]=true

很好,既然我们有了思路,便来开始实现代码

public String longestPalindrome(String s) {
    if(s == null || s.length() < 2)  return s;
        
    int lens = s.length();
    int MaxLen = 0; //回文串最大长度
    int start = 0;  //记录回文串开始的位置
    int end = 0;    //记录结束的位置
    boolean[][] pq = new boolean[lens][lens];  //记录l,r之间是否为回文
    for (int r = 1; r < lens; r++) {
	  for (int l = 0; l < r; l ++) {
	   if(s.charAt(r) == s.charAt(l) && (r - l < 2 || pq[l + 1][r - 1] == true)) {
		pq[l][r] = true;
		int len = r - l + 1;
		if(len > MaxLen) {
		    MaxLen = len;
			start = l;
			end = r;
		 }
	    }
      }
    }
    return s.substring(start,end + 1);
}

   代码看起来自然是相当的简单,但是解读起来就不是那么简单啦。首先,我们去遍历他本身,进行的是二重循环,这样我们可以得到 s 的所有子串。我们下面的判断

s.charAt(r) == s.charAt(l) && (r - l < 2 || pq[l + 1][r - 1] == true)

   我们可以看见,当s[r] = s[l]并且后面的两种情况是,

   1.r - l <2 就代表,r - l = 0,或者r - l = 1,那么等于 0 时,不正是r = l的时候嘛,就相当于回文串是奇数的情况,中间只有一个字符,而 r - l =1就对应回文串是偶数的情况,中间是两个字符,并且他们相等。

   2.pq[l + 1][r - 1] = true就很容易理解啦。我们判断 l ,r之间是否为回文,那么我们只需要两个条件,这也正是我们的状态转移方程 。状态转移方程,dp[l][r]=true并且(l-1)和(r+1)两个位置为相同的字符,此时dp[l-1][r+1]=true。

   之后的代码就很简单了,这里就不做讲解啦。


题解2:(中心扩散)

   这个中心扩散并非暴力解法,反而,此解法比动态规划花时间还要少。那我们了解一下他的思路。

   我们先回顾一下,在我们暴力求解时,我们需要分两种情况去讨论,这样让我们变得很麻烦,那我们看看他的共同之处,就是两端都是相同的(回文本身具有的性质)。那我们这样思考 

   我们把它看作中间全部是相同字符构成的,然后两端相同两端。分析一下,如果回文是偶数,那自然中间是两或多个相同的字符,那要是奇数呢?只有一个字符,那我们为什么不能把它看作也是相同字符构成的呢?只是只有一个罢了!

   很好,我们既然有了上面的概念,那我们来了解一下思路,其实思路也很简单,我们每一次都把中间的“相同的”字符找出来,然后再进行扩散,每一次去更新我们的开始位置和结束位置。并不像暴力解法一样,我们需要去比对s的所有子串是否是回文。

代码:

public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        //  保存起始位置,测试了用数组似乎能比全局变量稍快一点
        int[] range = new int[2];
        char[] str = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
         // 把回文看成中间的部分全是同一字符,左右部分相对称
         //  找到下一个与当前字符不同的字符
            i = findLongest(str, i, range);
        }
        return s.substring(range[0], range[1] + 1);
    }
    
    public static int findLongest(char[] str, int low, int[] range) {
         //  查找中间部分
        int high = low;
        while (high < str.length - 1 && str[high + 1] == str[low]) {
            high++;
        }
        // 定位中间部分的最后一个字符
        int ans = high;
        //从中间向左右扩散
        while (low > 0 && high < str.length - 1 && str[low - 1] == str[high + 1]) {
            low--;
            high++;
        }
        //记录最大长度
        if (high - low > range[1] - range[0]) {
            range[0] = low;
            range[1] = high;
        }
        return ans;
    }

在我们的主函数里,我们对s串进行了一次遍历,而其中的函数则是我们中心扩散的函数,思路就很简单了,以每一个字符为中心,两端阔山。那我们重点放到findLongest()函数讲解。

   1.我们首先找到了中间部分,我们将传过来的字符为起点,一路往后找相同的字符,while (high < str.length - 1 && str[high + 1] == str[low]) ,最好的情况当然是low往后全相同,但是我们还是得加以限制得。这个循环做完之后就代表 low -high 之间全部字符全部相同,即是我们上述说的所有回文看作中间由相同字符组成,当中心只有1个时,(回文长度为奇数)low = high;

   2.我们接下来的循环就是中心扩散啦,扩散过程还是比较简单,一个前移,一个后移。接着便是记录我们的最大值的起始位置和末位置

   3.你可能会发现我们忽略了一点,int ans = high;我们为什么记录下这个最高处呢?可以看到我们返回了 ans ,它将作为下一个进入此函数的点,因为我们又给了 i 。那为什么我们要这样呢?我们思考一下,如果我们找到了一串中心相同的即 low -high都相同,意思是 high + 1和他们肯定不同(这不用说了吧,因为第一个while要把所有连着并且相同的找完), 既然他们不相同,那么我们如果这次匹配失败,我们是不是还需要下次从 low+1开始呢?答案当然是不!因为下次我们进来的时候,它以同样的中心肯定是找不到相同的回文的。所以我们直接跳过这段相等的中心。如果你不明白,下面这张图估计能帮到你

每日算法---5. 最长回文子串(图1)

这应该也算一个小小的优化。

  

  当然,还有更快的方法。欢迎大家评论留言,互相交流,交流也是学习的过程嘛