Subject to introduce

Force buckle 5 questions: leetcode-cn.com/problems/lo…

Method 1: dynamic programming

For a substring, if it is a palindrome and its length is greater than 2, it is still a palindrome after removing the first and last two letters. For example, for the string “ababa”, if we already know that “bab” is a palindrome string, then “ababa” must be a palindrome string because it starts and ends with “A”.

According to this idea, we can use the method of dynamic programming to solve the problem. We use P(I,j) to represent the i-th through JTH letters of the string s.

Then we can write the state transition equation of dynamic programming:

The code is as follows:

public String longestPalindrome(String s) {
    if (s == null || s.length() < 2) {
        return s;
    }
    int strLen = s.length();
    int maxStart = 0;  // The starting point of the longest palindrome string
    int maxEnd = 0;    // End of the longest palindrome string
    int maxLen = 1;  // The longest palindrome string length

    boolean[][] dp = new boolean[strLen][strLen];

    for (int r = 1; r < strLen; r++) {
        for (int l = 0; l < r; l++) {
            // r-l <= 2 indicates that there is only one character between the two
            if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                dp[l][r] = true;
                if (r - l + 1 > maxLen) {
                    // Update the maximum value
                    maxLen = r - l + 1; maxStart = l; maxEnd = r; }}}}return s.substring(maxStart, maxEnd + 1);
}
Copy the code

Method two: center diffusion method

The first thing we should think about is, given a string s, how do we find a subroutine in S?

Here’s an interesting idea: since a palindrome string is a string that reads the same backwards and forwards, if we reverse s, call it s’, and then look for the longest common substring in s and S ‘, we should find the longest common substring.

For example, the string ABacd, and conversely, dcaba, their longest common substring is ABA, which is the longest loop substring.

For example, the string aacxycaa is reversed to aacyxcaa. The longest common substring is aac, but the longest loop substring should be AA.

Although this way of thinking is not correct, but this way of thinking about the problem into other forms is very worth advocating.

Here is the correct way to use a double pointer.

The core idea of finding palindromes is to judge palindromes by spreading from the middle to both sides. For the longest substring, this is what it means:

For 0 <= I < len(s): find a palindrome string centered around s[I]Copy the code

But, as we said, the palindrome string can be odd or even, and in the case of ABBA, without a central character, the algorithm is dead. So we can modify it:

For 0 <= I < len(s): find a palindrome centered on s[I] and s[I +1]Copy the code

PS: Readers may find the index here to be out of bounds, which will be dealt with later.

To find the longest palindrome string, implement a tricky function:

public String palindrome(String s ,int l ,int r) {
    // Prevent trespassing
    while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        // Expand to both sides
        l--;
        r++;
    }
    return s.substring(l + 1, r);
}
Copy the code

Why pass in two Pointers L and r? Because this implementation can handle both odd and even palindrome string lengths:

For 0 <= I < len(s): # palindrome(s, I, I) # palindrome(s, I, I) # palindrome(s, I, I +1) # palindrome(s, I, I +1Copy the code

The complete code is as follows:

class Solution {
    public String longestPalindrome(String s) {
        String result = "";
        for(int i = 0 ; i < s.length() ; i++) {
            String s1 = palindrome(s, i,i);
            String s2 = palindrome(s, i,i + 1);
            // Update the maximum value
            result = result.length() > s1.length() ? result : s1;
            // Update the maximum value
            result = result.length() > s2.length() ? result : s2;
        }
        return result;
    }

    /** * center extension method */
    public String palindrome(String s ,int l ,int r) {
        // Prevent trespassing
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            // Expand to both sides
            l--;
            r++;
        }
        return s.substring(l + 1, r); }}Copy the code

At this point, the problem of the longest substring is solved, O(N^2) in time, O(1) in space.

It is worth mentioning that this problem can be solved by dynamic programming with the same time complexity, but at least O(N^2) space complexity to store DP tables. This is a rare dynamic programming problem with a non-optimal solution.