Total Accepted: 200641 Total Submissions: 798974 Difficulty: Medium Contributor: LeetCode Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Given a string (with a maximum length of 1000), find its longest palindrome substring. You can assume that there is only one longest palindrome that satisfies this condition. The sample gives the string “abcdzdCAB”, whose longest substring is “CDZDC”.

Analysis of the

Method 1: the longest common substring

The easiest way to think about it is to reverse the string and find the largest common substring of both strings, which is the longest callback substring

public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
    public String longestCommonSubstring(String A, String B) {
        int n = A.length();
        int m = B.length();
        
        int[][] dp = new int[n+1][m+1];
        //dp[0][0] = 0;
        
        for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {if(A.charAt(i-1) == B.charAt(j-1))
        			dp[i][j] = dp[i-1][j-1] + 1;
        		else
        			dp[i][j] = 0;
        	}
        }
        int x = 0,y = 0;
        int max = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if(dp[i][j] > max) {
                	max = dp[i][j];
                	x = i-1;
                	y = j-1;
                }
            }
        }
        
        StringBuilder sb =new StringBuilder();
        while(x >=0 && y>=0) {
        	if(A.charAt(x) == B.charAt(y)) {sb.append(A.charAt(x)); x--; y--; }else
        		break;
        }
        
        return sb.reverse().toString();
    }
	
	public String longestPalindrome(String s) {
		if(s.length() == 0)
			return "";
		
		String sr = reverseStr(s);
		
		return longestCommonSubstring(s, sr);
		
	}
	
	public String reverseStr(String s) {
		StringBuilder sb = new StringBuilder(s);
		sb.reverse();
		returnsb.toString(); }}Copy the code

## Method 2: Dp [I][j]: a string from I to j is a palindrome string, true if it is a palindrome string, false if it is not a palindrome string Dp [I][j] = dp[I +1][J-1], this is according to the characteristics of the palindrome string, relatively easy to understand, for example, we know bab is a palindrome string, if a = a, then ababa is also a palindrome string! So we can use dynamic programming to find the longest palindrome string, and then we know where it starts, I and J, so it’s easier to solve. The only thing to notice is that we have to do it backwards instead of going backwards as usual, because the dependency of the state transition equation is backwards.

public String longestPalindrome(String s) {
  int n = s.length();
  String res = null;
    
  boolean[][] dp = new boolean[n][n];
    
  for (int i = n - 1; i >= 0; i--) {
    for (int j = i; j < n; j++) {
      dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
            
      if(dp[i][j] && (res == null || j - i + 1 > res.length())) { res = s.substring(i, j + 1); }}}return res;
}
Copy the code

Method three: two sides of the expansion method

We consider extending each character on both sides, looking for palindrome strings, and recording the length. There are two cases, bab, which extends from a to both sides, and ABba, which extends from the middle of BB to both sides.

public String longestPalindrome(String s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if(len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; }}return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}
Copy the code