LeetCode第五题之最长回文子串

悠悠 2022-05-26 02:29 151阅读 0赞

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

示例 1：

输入: "babad"
    输出: "bab"
    注意: "aba"也是一个有效答案。

示例 2：

输入: "cbbd"
    输出: "bb"

思路一：暴力寻找。

思路二：中心扩展法。

思路三：动态规划

寻找最长回文字符串

利用动态规划来求最长回文字符串经常要借助一个二维布尔数组，如图：

[![Java字符串——动态规划求最长回文字符串][Java]][Java_Java]  
每一个dp\[i\]\[j\]代表图中一个方格，每个方格中的T和F分别代表当前子串是否为回文字符串，如

dp\[1\]\[4\]="baab"，由定义,在初始状态可以完全确定图中上三角中方格的值。

**再回到回文字符串，如"balalab"，判定的原则为str\[0\] 等于 str\[6\] 并且"alala"为回文字符串，转换为数学表达式即是str\[i\] == str\[j\] && dp\[i+1\]\[j-1\]**。

这样我们就可以判定出所有的回文字符串，并且找出最长的回文字符串。

思路四：Manacher算法

首先说明一下，Manacher算法能够使得在O(n)的时间复杂度下找到最长的回文子串。

### (1).Manacher算法的概述 ###

Manacher算法只能解决长度为奇数的字符串，所以Manacher算法利用了一个比较巧妙的方法来同时解决长度为奇数或者偶数的字符串。Manacher算法通过转换字符串来实现的，例如：原来的字符串：abc，经过转换得到：\#a\#b\#c\#，这样原来的字符串长度不管是奇数还是偶数，最终转换都能够得到一个长度为奇数的字符串。  
  其次，Manacher算法通常还需要一个数组(我们假设是，len数组)来记录每一个字符在原字符串中的回文字符串的最大长度，其实实际上是，该字符在原来的字符串中得到的最长回文字符串的一半长度。  
  例如：aba，经过转换得到：\#a\#b\#a\#，b能得到的最长回文字符串是：\#a\#b\#a\#，我们假设b的下标是i，得到的最长字符串的第一个字符下标是left，最后一个字符的下标是right那么b对应的值是：right - i + 1；  
  同时，我们还能知道的是，i对应的字符得到的最大回文子串长度是：len\[i\] - 1,例如：上面的例子，b的下标是3，所以len\[3\] = 4,那么b对应的回文字符串aba，长度恰好是len\[3\] - 1 = 3。这个是为什么呢？我们假设原来的字符串为oldString(没有经过转换的)，转换过后的字符串为newString，假设oldString长度为length，那么newString的长度就为2 \* length + 1,所以得到的字符串长度肯定为奇数。对于newString中的第i个字符对应的回文字符串，长度肯定为2 \* len\[i\] - 1(这个你们可以简单的去举例子测试一下)，同时，经过观察得知，2 \* len\[i\] - 1个字符中，肯定有len\[i\]个是\#,其余的才是正常的符号，因为在所有的回文字符串中\#的个数总是与其他符号的个数相差为1。

### (2).len数组的计算 ###

首先，我们从左往右计算len\[i\]，当我们计算len\[i\]时，len\[j\]已经计算完毕(0 < j < i)。  
  我们假设，在已经计算了的字符当中取得最长回文子串的右端点的最大值(该回文字符串不一定是最长的回文字符串，只是要求该回文字符串右端下标最大)，假设最大值为rightIndex，并且设置该回文子串中心的位置是centerIndex，那么分为两种情况：

#####   A.i < rightIndex #####

我们假设以centerIndex为中心，与i对应的是j。如图:

![Image 1][]

我们知道的是，以centerIndex为中心，回文字符串能达到rightIndex，那么此时有分为两种情况：  
  如果i + len\[j\] < P,也就是说，以j为中心的回文字符串在以centerInde为中心的回文字符串内部，此时可以得到以j为中心的回文字符串与以i为中心的回文字符串是相同的，为什么呢？因为他们在以centerIndex为中心的回文字符串的内部。所以可以得到的是，len\[i\] = len\[j\]。  
  如果i + len\[j\] >= P的话，也就是说，以i为中心的回文字符串有一部分在以centerIndex为中心的回文字符串的外部，此时外部这一部分需要我们一个一个的计算。

#####   B.i > rightIndex #####

如果i > rightIndex的话，那就说明，以i为中心的回文字符串一点都没有匹配。所以需要我们一个一个的匹配了。

代码：

public class LongestPalindrome {
    
    	private static int max = 0;
    	private static String res = "";
    
    	public static String longestPalindrome1(String s) {
    		for (int size = s.length(); size > 0; size--) {
    			for (int low = 0, high = low + size - 1; high < s.length(); low++, high++) {
    				if (shrinkCheckPalindrome(s, low, high)) {
    					return s.substring(low, high + 1);
    				}
    			}
    		}
    		return s.substring(0, 1);
    	}
    
    	public static boolean shrinkCheckPalindrome(String s, int low, int high) {
    		while (low <= high) {
    			if (s.charAt(low) == s.charAt(high)) {
    				low++;
    				high--;
    			} else {
    				return false;
    			}
    		}
    		return true;
    	}
    
    	public static String longestPalindrome2(String s) {
    
    		if (s.length() == 1) {
    			return s;
    		}
    		for (int i = 0; i < s.length() - 1; i++) {
    			checkPalindrome(s, i, i);
    			checkPalindrome(s, i, i + 1);
    		}
    		return res;
    	}
    
    	public static void checkPalindrome(String s, int low, int high) {
    		while (low >= 0 && high < s.length()) {
    			if (s.charAt(low) == s.charAt(high)) {
    				if (high - low + 1 > max) {
    					max = high - low + 1;
    					res = s.substring(low, high + 1);
    				}
    				low--;
    				high++;
    			} else {
    				return;
    			}
    		}
    	}
    
    	public static String longestPalindrome3(String s) {
    		int len = s.length();
    		if (s == null || len == 0) {
    			return s;
    		}
    		String res = "";
    		int max = 0;
    		// 创建一个行列均为字符串长度的二维数组，创建时默认初始化为false
    		boolean[][] dp = new boolean[len][len];
    		for (int j = 0; j < len; j++) {
    			for (int i = 0; i <= j; i++) {
    				// 这里只考虑了i<=j的情况，因为i>j时均为false
    				// 当i==j,j-i==1,j-i==2时，只要满足s.charAt(i) == s.charAt(j)就是回文字符串
    				// 如果不是这样，还要判断当前回文字符串的子串是不是回文字符串，即dp[i + 1][j - 1])，这就是动
    				// 态规划思想
    				dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1]);
    				if (dp[i][j]) {// 如果是回文字符串
    					if (j - i + 1 > max) {// 并且比之前的回文字符串要长，更新字符串长度，记录字符串
    						max = j - i + 1;
    						res = s.substring(i, j + 1);
    					}
    				}
    			}
    		}
    		return res;
    	}
    
    	public static String longestPalindrome4(String s) {
    		// -----------------------------------
    		// 转换字符串
    		StringBuilder stringBuilder = new StringBuilder();
    		stringBuilder.append("#");
    		for (int i = 0; i < s.length(); i++) {
    			stringBuilder.append(s.charAt(i));
    			stringBuilder.append("#");
    		}
    		// -----------------------------------
    		int rightIndex = 0;
    		int centerIndex = 0;
    		// 求len中的最大
    		int answer = 0;
    		// answer最大时的中心
    		int index = 0;
    		int len[] = new int[stringBuilder.length()];
    		for (int i = 1; i < stringBuilder.length(); i++) {
    			// 当rightIndex > i，那么我们就在rightIndex - i 与len[2 * centerIndex - i](len[j])，取得最小值
    			// 因为当i + len[j] < rightIndex时，我们就把len[i]更新为len[j]
    			// 但是如果i + len[j] >= rightIndex时，我们暂且将len[i]定更新为rightIndex - i,超出的部分需要我们一个一个的匹配
    			if (rightIndex > i) {
    				len[i] = Math.min(rightIndex - i, len[2 * centerIndex - i]);
    			} else {
    				len[i] = 1;
    			}
    			// 一个一个匹配
    			// 要么是超出的部分，要么是i > rightIndex
    			while (i - len[i] >= 0 && i + len[i] < stringBuilder.length()
    					&& stringBuilder.charAt(i - len[i]) == stringBuilder.charAt(i + len[i])) {
    				len[i]++;
    			}
    			// 当 len[i] + i > rightIndex,我们需要更新centerIndex和rightIndex
    			// 至于为什么会这样做，理解一下rightIndex和centerIndex的含义
    			if (len[i] + i > rightIndex) {
    				rightIndex = len[i] + i;
    				centerIndex = i;
    			}
    			if (len[i] > answer) {
    				answer = len[i];
    				index = i;
    			}
    		}
    		// 截取字符串
    		// 为什么index - answer + 1,因为len[i] - 1才是原来的回文字符串长度，而answer记录的是len中最大值
    		return stringBuilder.substring(index - answer + 1, index + answer).replace("#", "");
    
    	}
    
    	public static void main(String[] args) {
    		String s = "abcdad";
    		System.out.println(longestPalindrome4(s));
    	}

GitHub地址： [https://github.com/xckNull/Algorithms-introduction][https_github.com_xckNull_Algorithms-introduction]

[Java]: http://s13.sinaimg.cn/bmiddle/004lhYeDzy7jvJIixn6ec&690
[Java_Java]: /images/20220526/f748dd52cf98459cae4ac80cf73b93be.png
[Image 1]: 
[https_github.com_xckNull_Algorithms-introduction]: https://github.com/xckNull/Algorithms-introduction