One brush 148 force deduction hot question-5 longest palindrome substring (m)

 subject ：
 Give you a string  s, find  s  The longest palindrome substring in .
-------------
 Example ：
 Input ：s = "babad"
 Output ："bab"
 explain ："aba"  It's the same answer .
 Example  2：

 Input ：s = "cbbd"
 Output ："bb"
 
 Tips ：

1 <= s.length <= 1000
s  It consists only of numbers and English letters 
-----------------------
 reflection ：
 Dynamic programming method ：
 Palindromes naturally have 「 State shift 」 nature ： A length is strictly greater than  22  After removing the first and last characters of the palindrome ,
 The rest is still palindrome . conversely , If the first and last two characters of a string are not equal , Then this string must not be a palindrome .
「 Dynamic programming 」 According to this property, we get .

 The first  1  Step ： Define the State 
dp[i][j]  Express ： Substring  s[i..j]  Whether it is palindrome substring ,
 Here's the substring  s[i..j]  Defined as left closed right closed interval , That is, you can get  s[i]  and  s[j]

 The first  2  Step ： Think about the state transfer equation 
 According to whether the first and last characters are equal , Need classified discussion ：

dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

 explain ：
「 Dynamic programming 」 Of 「 Bottom up 」 Ideas for solving problems , Most of the time, I am filling in a two-dimensional form .
 because  s[i..j]  Express  s  A string of , therefore  i  and  j  The relationship is  i <= j, Just fill in the part above the diagonal of this form ;
 notice  dp[i + 1][j - 1]  You need to consider special circumstances ：
 If you remove  s[i..j]  Two character substrings at the beginning and end  s[i + 1..j - 1]  The length of is strictly less than  2（ It doesn't form an interval ）,
 namely  j - 1 - (i + 1) + 1 < 2  when ,
 Put it in order  j - i < 3, here  s[i..j]  Whether it is palindrome only depends on  s[i]  And  s[j]  Whether it is equal or not .
 The conclusion is also intuitive ：j - i < 3 Equivalent to  j - i + 1 < 4,
 That is, when the sub string  s[i..j] The length of is equal to  2  Or equal to  3  When ,
s[i..j]  Whether it is a palindrome is determined by  s[i]  And  s[j]  Equality determines .

 The first  3  Step ： Consider initializing 
 A single character must be a palindrome string , So initialize the diagonal to  true, namely  dp[i][i] = true.
 According to the first  2  Description of step ： When  s[i..j]  The length of is  22  when , Just judge  s[i]  Is it equal to  s[j],
 Therefore, the values on the diagonal of the two-dimensional table will not be referenced . So don't set  dp[i][i] = true  You can also get the right conclusion .

 The first  4  Step ： Consider output 
 Once you get it  dp[i][j] = true, Just record the substring 「 length 」 and 「 The starting position 」.
 There's no need to intercept , This is because intercepting strings also has performance consumption .

 This principle should be followed in filling out the form ： Always get whether the small string is the result of palindrome first ,
 Then the large substring can refer to the judgment result of the small substring , So the order of filling in the form is very important ;
 Code ：
 class Solution {
    
    public String longestPalindrome(String s) {
    
        int len = s.length();// Define variables to represent   String length 
        if (len < 2) {
    //  If the string length is less than 2  Returns the string directly 
            return s;
        }

        int maxLen = 1;// Define variables to represent   Number of palindrome characters 
        int begin = 0;// Start index of palindrome substring 

        // dp[i][j]  Express  s[i, j]  Is it a palindrome string 
        boolean[][] dp = new boolean[len][len];// Define two-dimensional array storage   All possible results 

        for (int i = 0; i < len; i++) {
    // A single character is itself a palindrome string 
            dp[i][i] = true;
        }
        for (int j = 1; j < len; j++) {
    // Recursive traversal ：  All elements above the diagonal of a two-dimensional array 
            for (int i = 0; i < j && i < len - 1; i++) {
    
                if (s.charAt(i) != s.charAt(j)) {
    // If two characters are not equal   It's not a palindrome string 
                    dp[i][j] = false;
                } else {
    // When it is a palindrome string , The number of characters is less than or equal to 3 individual   It's a palindrome string 
                    if (j - i < 3) {
    
                        dp[i][j] = true;
                    } else {
    // Recursive judgment ： When the characters on both sides of the boundary are equal , Continue to determine whether the characters in the inner layer are equal 
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
 //  as long as  dp[i][j] == true  establish , It means substring  s[i..j]  It's palindrome. , At this point, record the palindrome length and starting position 
                if (dp[i][j] && j - i + 1 > maxLen) {
    
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        // String cutting 
        return s.substring(begin, begin + maxLen);
    }
}
 Complexity analysis ：
 Time complexity ：O(N^{
    2}), here  N  Is the length of the string ;
 Spatial complexity ：O(N^{
    2})  A two-dimensional table is used to record all possible situations 

LC