Topic describes

Given a string s, find the longest substring in s.

Example 1:

Input: s = "babad" Output: "bab" Explanation: "ABA" is also the answer to the question.Copy the code

Example 2:

Input: s = "CBBD" Output: "bb"Copy the code

Example 3:

Input: s = "a" Output: "a"Copy the code

Example 4:

Input: s = "AC"Copy the code

Tip:

  • 1 <= s.length <= 1000
  • S consists of only numbers and English letters (uppercase and/or lowercase)

Source: LeetCode link: leetcode-cn.com/problems/lo… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

The easiest way to think about this is to go through it by force, take out all the substrings, and determine if each substring is a callback substring. When it is a subroutine, fetch the longest subroutine.

class Solution {
    String result = "";

    public String longestPalindrome(String s) {
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String temp = s.substring(i, j);
                if(isPaindrome(temp)) { result = result.length() > temp.length() ? result : temp; }}}return result;
    }

    private boolean isPaindrome(String temp) {
        StringBuilder sb = new StringBuilder(temp);
        returntemp.equals(sb.reverse().toString()); }}Copy the code

The time complexity of this solution is O(n2), but AFTER I submit it, THE time is out of limit. Efficiency is the enemy after all.

The second idea is that as I walk through each element, I try to find out if the left and right sides of the current element are symmetric. All the way up to asymmetry, and that substring is a callback substring, which means that for every element, I get at least one callback substring of length 1. If the length of the substring is odd, then the current element must be the middle element, but if it is even, then the current element may be left or right of the middle element. We define two cursors left and right to represent the left and right elements of the current element.

public String longestPalindrome(String s) {

        if (s == null || s.length() == 0) {
            return "";
        }
        int strLen = s.length();
        int left = 0;
        int right = 0;
        int len = 1;
        int maxStart = 0;
        int maxLen = 0;

        for (int i = 0; i < strLen; i++) {
            left = i - 1;
            right = i + 1;
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                len++;
                left--;
            }
            while (right < strLen && s.charAt(right) == s.charAt(i)) {
                len++;
                right++;
            }
            while (left >= 0 && right < strLen && s.charAt(right) == s.charAt(left)) {
                len = len + 2;
                left--;
                right++;
            }
            if (len > maxLen) {
                maxLen = len;
                maxStart = left;
            }
            len = 1;
        }
        return s.substring(maxStart + 1, maxStart + maxLen + 1);

    }
Copy the code

There is still a lot of double counting in this solution. We can further consider the practice of dynamic programming, most of the idea of dynamic programming is to add a memo to maintain the results of each calculation.

We use a Boolean dp[l][r] to indicate whether the string from I to j is a palindrome. If dp[l][r]=true, we need to determine whether dp[L-1][r+1] is a palindrome. You just need to determine whether the string is the same character at (L -1) and (r+1).

The final code

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++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1; maxStart = l; maxEnd = r; }}}}return s.substring(maxStart, maxEnd + 1);

    }
Copy the code

By ReedFan link: leetcode-cn.com/problems/lo…

conclusion

There are many ideas in this topic, the first two are easy to think of, dynamic programming I refer to the solution of other coder, feel that the most important thing in this topic is to understand the initial state and state transfer conditions. If l=r, dp[l][r]=true. Dp [L][r]=true and (L -1) and (r+1) are the same character, dp[L -1][r+1]=true.

This article is participating in “Digging gold in April 2021 swipe card”, click to see the activity details. Give it a thumbs up if you like.