我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 5. 最長迴文子串

題目

給定一個字元串 s，找到 s 中最長的迴文子串。你可以假設 s 的最大長度為 1000。

示例 1：

輸入: "babad"
輸出: "bab"
註意: "aba" 也是一個有效答案。

示例 2：

輸入: "cbbd"
輸出: "bb"

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

本題有三種思路解法：

• dp動態規劃
• 中心擴展
• Manacher/馬拉車演算法

其中，前兩種時間複雜度都是\(O(n^{2})\)，最後一種是\(O(n)\)的，目前最優解；

思路1-dp動態規劃

思路解析：dp的思路是若\([i] == [j]\)，那麼讓\([i, j]\)是迴文就必須有\([i + 1] == [j - 1]\)；
即dp的動態方程為：

\[dp[i, j] = dp[i + 1, j - 1] and ([i] == [j] || j - i < 3) \]

對於\(j - i < 3\)的解釋：當最後的只剩單個字元時，作為迴文的中心字元免驗證；

演算法複雜度:

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(n^{2}\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $

思路2-中心擴展

思路解析：首先把字元串的所有連續相等的字元都壓縮看為一個字元，那麼對每一個字元嘗試左右擴展迴文長度即可；

核心思想：將所有連續相等的字元看為迴文的最中心字元，避免了對奇偶數的區別計算；

演算法複雜度:

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(n^{2}\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $

思路3-Manacher/馬拉車演算法

待研究...

演算法複雜度:

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $

演算法源碼示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2019年12月10日 下午2:30:25 
 * @Description: 5. 最長迴文子串
 *
 */
public class LeetCode_0005 {

}

class Solution_0005 {
	/**
	 * @author ZhouJie
	 * @date 2019年12月10日 下午3:07:18 
	 * @Description: TODO(方法簡述) 
	 * @return String 
	 * @UpdateUser-UpdateDate:[ZhouJie]-[2019年12月10日 下午3:07:18]  
	 * @UpdateRemark:1-動態規劃
	 *
	 */
	public String longestPalindrome_1(String s) {
		int len = 0;
		if (s == null || (len = s.length()) < 2) {
			return s;
		}
		boolean[] p = new boolean[len];
		int[] range = new int[2];
		for (int i = len - 1; i >= 0; i--) {
			for (int j = len - 1; j >= i; j--) {
				// j-i考慮到 像OO和OHO最後中心的奇偶問題
				p[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || p[j - 1]);
				if (p[j] && (j - i > range[1] - range[0])) {
					range[0] = i;
					range[1] = j;
				}
			}
		}
		return s.substring(range[0], range[1] + 1);
	}

	/**
	 * @author ZhouJie
	 * @date 2019年12月10日 下午3:34:44 
	 * @Description: TODO(方法簡述) 
	 * @return String 
	 * @UpdateUser-UpdateDate:[ZhouJie]-[2019年12月10日 下午3:34:44]  
	 * @UpdateRemark:2-中心擴展--優化後
	 *
	 */
	public String longestPalindrome_2(String s) {
		if (s == null || s.length() < 2) {
			return s;
		}
		int[] range = new int[2];
		char[] cs = s.toCharArray();
		for (int i = 0; i < cs.length; i++) {
			// 把迴文看成中間部分都是同一字元且左右對稱，尋找下一個與當前字元不同的位置
			i = fastMove(cs, i, range);
			// 若剩餘長度不足已知最大長度的一半時，直接跳出迴圈
			// 剩餘長度的下一個起始計算位置為i+1，以為i+1為中心的剩餘最長迴文為(length-1-(i+1))*2+1
			// 即 (lenght-i-2)*2+1，一隻的最大長度為range[1]-range[0]+1
			// 所以判定條件為 (lenght-i-2)*2+1<range[1]-range[0]+1
			// 即(lenght-i-2)*2<range[1]-range[0]
			if ((cs.length - i - 2) * 2 < (range[1] - range[0])) {
				break;
			}
		}
		return s.substring(range[0], range[1] + 1);
	}

	private int fastMove(char[] cs, int low, int[] range) {
		int high = low;
		int len = cs.length;
		// 尋找下一個與low不等的字元
		while (high < len - 1 && cs[high + 1] == cs[low]) {
			high++;
		}
		int nextI = high;
		// 開始校驗左右擴散校驗
		while (low > 0 && high < len - 1 && cs[low - 1] == cs[high + 1]) {
			low--;
			high++;
		}
		if (high - low > range[1] - range[0]) {
			range[0] = low;
			range[1] = high;
		}
		return nextI;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年5月22日 下午9:47:36 
	 * @param: @param s
	 * @param: @return
	 * @return: String
	 * @Description: 3-Manacher演算法--待研究
	 *
	 */
	public String longestPalindrome_3(String s) {
		return null;
	}
}