leetcode-5-最長回文子串(longest palindromic substring)-java

題目及測試

package pid005;
/*最長回文子串

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

示例 1：

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

示例 2：

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






*/
public class main {
	
	public static void main(String[] args) {
		String[] testTable = {"babad","cbbd","ccc","eabcb"};
		for (int i=0;i<testTable.length;i++) {
			test(testTable[i]);
		}
	}
		 
	private static void test(String ito) {
		Solution solution = new Solution();
		String rtn;
		long begin = System.currentTimeMillis();
		System.out.println("ito="+ito);
		rtn = solution.longestPalindrome(ito);//執行程式
		long end = System.currentTimeMillis();		
		System.out.println("rtn="+rtn);
		System.out.println();
		System.out.println("耗時：" + (end - begin) + "ms");
		System.out.println("-------------------");
	}

}
           

解法1（成功，138ms，很慢）

對0到length-1進行循環（不能循環到中間，因為字元串後半段也有可能有會文字元串）

對每個index，進行奇數會文和偶數會文的判斷，奇數是兩邊相等，偶數是自身與右邊相等

記錄max的length和substring

package pid005;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

public class Solution {
public String longestPalindrome(String s) {
    int length=s.length();
    if(length<=1){
    	return s;
    }
    int maxLength=0;
    String maxString="";
    for(int i=0;i<length;i++){//4 2(1)  5 3(2)
    	//首先檢查以自己為中心（奇數會文）
    	int j=1;
    	int nowlength=1;
    	while(i-j>=0&&i+j<length){
    		if(s.charAt(i-j)==s.charAt(i+j)){
    			j++;
    			nowlength=nowlength+2;
    		}
    		else{
    			break;
    		}
    	}    	
    	if(nowlength>maxLength){
    		maxString=s.substring(i-(int)Math.floor(nowlength/2), i+(int)Math.floor(nowlength/2)+1);
    		maxLength=nowlength;
    	}
    	//檢查偶數會文
    	j=0;
    	nowlength=0;
    	while(i-j>=0&&i+j+1<length){
    		if(s.charAt(i-j)==s.charAt(i+j+1)){
    			j++;
    			nowlength=nowlength+2;
    		}
    		else{
    			break;
    		}
    	}
    	if(nowlength>maxLength){
    		maxLength=nowlength;
    		maxString=s.substring(i-nowlength/2+1, i+nowlength/2+1);
    	}
    	
    }
    
	return maxString;
    }

}
           

解法2（别人的）

動态規劃：

（一般含“最XX”等優化詞義的題意味着都可以動态規劃求解），時間複雜度O(n^2)，空間複雜度O(n^2)。

 形如"abba", "abbba"這樣的字元串，如果用dp[i][j]表示從下标i到j之間的子字元串所構成的回文子串的長度，則有：

 dp[i][j] = dp[i+1][j-1] && s[i] == s[j]

初始化：

 奇數個字元：dp[i][i] = 1; 偶數個字元：dp[i][i+1] = 1

若長度相同，傳回最後一個子串

public String longestPalindrome(String s) {
		if (s == null || s.length() <= 1)
			return s;
		int n = s.length();
		char[] cs = s.toCharArray();
		int max = 1;
		int maxIndex = 0;
		boolean dp[][] = new boolean[n][n];
		// 初始化一個字母
		for (int i = 0; i < n; i++) {
			dp[i][i] = true;
			maxIndex = i;
		}
		// 初始化兩個相同的字母"aa"
		for (int i = 0; i < n - 1; i++)
			if (cs[i] == cs[i + 1]) {
				dp[i][i + 1] = true;
				// 傳回最後一為2的子串
				max = 2;
				maxIndex = i;
			}
		// 從長度3開始操作, (aba)ba, a(bab)a, ab(aba)
		for (int len = 3; len <= n; len++)
			for (int i = 0; i < n - len + 1; i++) {
				// j為從i~i + len - 1下标，長度為len
				int j = i + len - 1;
				// 字元相同，并且内部長度是回文
				if (cs[i] == cs[j] && dp[i + 1][j - 1]) {
					max = len;
					// 因為長度遞增，如果之後的的能進入這裡都是比之前長的，
					// 是以不需要判斷大小
					maxIndex = i;
					dp[i][j] = true;
				}
			}
		return s.substring(maxIndex, maxIndex + max);
	}
           

解法3（别人的）

使用manacher算法

https://blog.csdn.net/xushiyu1996818/article/details/100533618