This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

preface

The fifth buckle is as follows:

A, thinking

First of all, we need to know what is an anthesis sub-string, the definition is as follows: anthesis sub-string: orthotopic and reverse reading is the same, such as ABCDCBA, orthotopic is abCDCBA reverse reading is also ABCDCBA

From the title, we can learn the following two information:

  • Input: string
  • Output: longest loop substring
  • Target: Find all the substrings of this string, except the longest.

If you take a closer look at the subroutine, you’ll see that adding the same characters left and right to the subroutine still forms the subroutine. For example, adding b to both sides of CDC is BCDCB, which is still a subroutine.

Assume that the string array is STR, with I and j representing subscripts

If STR [I] ~ STR [j] is a subroutine, there are two cases

  • str[i] ! = STR [j] : not a substring of a text
  • STR [I] == STR [j] : If STR [I +1] ~ STR [j-1] is a subroutine, it is a subroutine

Obviously, this problem can be solved using dynamic programming. The following state transition equation can be obtained:

Dp [I][j] : indicates whether I ~ j is a subroutine STR [] : indicates an array of strings

Equation of state: dp [I] [j] = dp [I + 1] [1] && STR [I] = = STR [j].

Second, the implementation

Optimization: Ignore the lower-left element because the substring is symmetric

Code implementation

    /** * dynamic programming: the longest substring ** /
    public String longestPalindrome(String s) {
        // In special cases, return directly
        if ("".equals(s)) {
            return null;
        }

        int[][] dp = new int[s.length()][s.length()];

        int begin = 0;  // The starting position of the substring
        int maxLen = 1; // Maximum length of substring (minimum 1)

        // Start filling in the form (from the top left corner of the form), ignoring the diagonals
        for (int j=0; j<s.length(); j++) {
            for (int i=0; i<=j; i++) {
                / / diagonal
                if (i == j) {
                    dp[i][j] = 1;
                } else {
                    boolean b = s.charAt(i) == s.charAt(j);
                    // Adjacent and equal
                    if (i+1==j && b) {
                        dp[i][j] = 1;
                    } else if (b && dp[i+1][j-1] = =1) {
                        dp[i][j] = 1;
                    }
                    // Since the int array defaults to 0, we can omit else here

                    // Determine whether the substring needs to be updated
                    if (dp[i][j] == 1 && j-i+1>maxLen){
                        maxLen=j-i+1; begin=i; }}}}return s.substring(begin, begin+maxLen);
    }
Copy the code

Third, summary

Today is the fifth buckle ~ this series will update the buckle 1-10 questions, continuous update for 10 days! Dig gold coin, I come 😁