A, answer key

Given a string s, find the longest subroutine in s. You can assume that the maximum length of s is 1000.

Example 1:

Input: “babad”

Output: “bab” Note: “ABA” is also a valid answer.

Example 2:

Input: “CBBD”

Output: “bb”

Brute force solutions, they run out of time, they have to think about dynamic programming,

Dynamic Programming Reference: What is dynamic programming

Boolean [][] flag, flag[I][j] indicates whether the string I through j is palindrome.

Boundary: a string of length 1 is TRUE

Optimal substructure (assuming the flag [I] [j] said string I to j the longest palindrome string) : flag [I] [j] = Max {flag [I + 1] [1], j – I}

State transition:

flag[i][i] = true flag[i][j] = max{flag[i+1][j-1],j-i}

When determining flag[I][j], it is necessary to ensure that flag[I +1][J-1] has been determined, so it is necessary to traverse in descending order of I and ascending order of J

Second, the code

public class Test {
    public static void main(String[] args) {
        String s = "babad";
        String palindrome = longestPalindrome(s);
        System.out.println(palindrome);
    }

    private static String longestPalindrome(String s) {
        if (s.isEmpty()) {
            return s;
        }
        int length = s.length();
        // represents the left and right subscripts of a string
        int left = 0, right = 0;
        // The initial two-dimensional array flag[I][j], indicating whether the string I to j is palindrome
        boolean[][] flag = new boolean[length][length];
        for (int i = length - 2; i >= 0; i--) {
            flag[i][i] = true;
            for (int j = i + 1; j < length; j++) {
                // If the character of string I is equal to the character of j and the internal character string flag[I +1][j-1] is also a palindrome, the characters from I to j are TRUE
                //(j-i<3) aba must be palindrome
                flag[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || flag[i + 1][j - 1]);
                // Find the longest palindrome string
                if(flag[i][j] && right - left < j - i) { left = i; right = j; }}}return s.substring(left,right+1); }}Copy the code

Third, summary

  1. Dynamic programming requires a good understanding of: boundaries, optimal substructures, state transitions
  2. Extract the i-th character of the string:s.charAt(i)
  3. The intercept length is (right-left) string:s.substring(left,right+1)