Topic describes

Method 1: dynamic programming

Train of thought

  • boolean dp[i][j]Representation strings[i,j]Is it a palindrome string

Thoughts on state transition equations

  • ifdp[i+1][j-1]fortrueAnd,s[i]=s[j],dp[i][j]Also for thetrue.
  • Next, we need to consider the boundary case,i+1 <= j-1Must be established, i.ej-i >= 2.j-i < 2For the condition of thes[i,j]Is a single character or two characters.
  • So it is concluded that the equation of state: dp [I] [j] = (s = s [j] [I]) && (dp + 1] [I] [j – 1 | | j – I < = 1)

Or draw a picture to understand the state transition equation

class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        boolean dp[][] = new boolean[length][length];
        int maxLen = 1;// The current maximum length
        int begin = 0;// Start index
        for (int j = 0; j < length; j++) {// Fill the column first, then fill the row, so that the lower left corner is clear.
            for (int i = 0; i < j; i++) {
                if(s.charAt(i) ! = s.charAt(j)) {// Write the simple case first
                    dp[i][j] = false;
                } else {
                    if (j - i <= 1) {// No lower left reference grid, one or two characters
                        dp[i][j] = true;
                    } else {// The current string must have at least three characters, which can be subtracted at both ends
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                    Dp [I][j] is a palindrome
                    if (dp[i][j] == true && j - i + 1 >= maxLen) {
                        maxLen = j - i + 1;
                        begin = i;
                        // res = s.substring(i, j + 1); // If both are false, there is no way to enter}}}}return s.substring(begin, begin + maxLen);// Get the starting point and length above, cut here}}Copy the code

Method two: Central extension

The opposite of the enumeration of violence 

class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        if (length <= 1) {
            return s;
        }
        int maxLength = 1;
        int begin = 0;
        for (int i = 0; i < length; i++) {// Iterate over the string s, treating each bit as the center of the extension
            int pLengthOdd = expand(s, i, i);// Expand to find odd palindrome strings centered on the number indexed by I
            int pLengthEven = expand(s, i, i + 1);// Expand to find an even palindrome string centered on the number indexed by I
            int pLength = Math.max(pLengthOdd, pLengthEven);
            if (pLength > maxLength) {
                maxLength = pLength;
                begin = i - (maxLength - 1) / 2; }}return s.substring(begin, begin + maxLength);
    }

    // Extend the search to return the longest callback substring
    public int expand(String s, int left, int right) {
        while (left >= 0 && right <= s.length() - 1) {
            if (s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            } else {
                break; }}return right - left - 1;// Notice the return value here
    }
Copy the code