Interview high frequency algorithm question --- longest palindrome substring

Catalog

subject

Topic analysis

Code implementation

Code parsing

Complexity analysis

---

subject

Topic link ： Longest text substring

Give a string s, find s The longest palindrome substring in

Topic analysis

So-called Palindrome Namely “ Fog locks the mountain ”,“ Day after day, tail water with sky ” , Namely Positive and negative are the same

such as “abcdcba”, We found that this is a palindrome string ,“bcdcb” It's also a palindrome string ,“cdc” It's also a palindrome string ,“d” It's also a palindrome string , We can find a law ： A palindrome string is also a palindrome string without a header and a tail

So we can use Dynamic programming To solve this problem

F(i,j) Representation string s Of the i To the first j A string of characters ,F(i,j)=true Indicates a palindrome string ,F(i,j)=false Indicates that it is not a palindrome string
From the above explanation, we can know if F(i+1,j-1) Palindrome string , And satisfy the string s Of the i And the j The characters are equal , that F(i,j) Is a palindrome string

So we can write dynamic programming State transition equation ：F(i,j) = F(i+1,j-1) && (Si==Sj), This equation means ：F(i+1,j-1) Is a palindrome string and s Of the i Characters and the j The characters are equal F(i,j) Is the palindrome string

Code implementation

public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        int maxLen = 1; // Maximum length of palindrome substring 
        int begin = 0; // The starting position of the palindrome substring 
        if(len < 2){ // If the string has only one element , So it must be palindrome string 
            return s;
        }
        //dp[i][j] Express s Of the i One to the first j Whether a character is a palindrome string 
        boolean[][] dp = new boolean[len][len]; 
        for(int i = 0;i < len;i++){ // The length is 1 The substring of is palindrome string 
            dp[i][i] = true;
        }
        char[] arr = s.toCharArray();
        for(int L = 2;L <= len;L++){  //L Is the length of the substring 
            for(int i = 0;i < len;i++){ //i Is the leftmost subscript of the substring 
                int j = L + i - 1; //j Is the rightmost subscript of the substring 
                if(j >= len){ // The subscript crossing the line , Exit loop 
                    break;
                }
                if(arr[i] != arr[j]){ // The first and last characters of the substring are not equal , Definitely not a palindrome string 
                    dp[i][j] = false;
                }else {
                    // When the first element of the substring is equal 
                    if(j - i < 3){  // If the substring length is 2,3 when , It's a palindrome string 
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1]; // if dp[i+1][j-1] A palindrome string is a palindrome string 
                    }
                }
                if(dp[i][j] && j-i+1>maxLen){ // Update the length of the maximum palindrome substring and the starting position of the substring 
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen); // from s Intercepts the largest palindrome substring in and returns 
    }
}

Code parsing

 

Complexity analysis

Time complexity ： Length of external loop substring , The starting value of the inner loop substring , Double loop nesting , The time complexity is O(n^2) 

Spatial complexity ： Storage space for dynamic planning dp[len][len], So the complexity of space is O(n^2)