This is the 16th day of my participation in the More text Challenge. For more details, see more text Challenge

Longest return substring (Question No. 5)

The title

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

Example 1:

Input: s = "babad" Output: "bab" Explanation: "aba" is also a correct answer.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" Output: "a"Copy the code

Tip:

  • 1 <= s.length <= 1000
  • sConsists only of numbers and letters (upper and/or lower case)

link

Leetcode-cn.com/problems/lo…

explain

Oh, this one. This one is one move short.

In fact, almost can be made, but there is still a point did not think, finally give up.

This problem has a total of three solutions, the author thought of the second, the first DP official said very detailed, but I really can not understand, really read for a long time, the train of thought can be understood, but the code is a little confusing.

The third solution is a mathematical formula, giving up decisively and not wanting to challenge it.

The rest is the second way, which is also the method I thought of from the beginning.

Center extension method, the method is very simple, is from the middle to both sides to find, judge whether the left and right are equal, equal to continue to expand, not equal to GG.

This method is very simple on the surface, and the key is to consider the middle may be two letters, sometimes in the middle is a letter, sometimes two letters, will be processed at this time, the author first idea is to determine when two letters are in the first or last, and then processed, logic is a little bit round, GG finally or less consider the result.

In fact, you should not compare them together at all. Each time you loop to a letter, you should consider whether the center point is one letter or two letters, and take the maximum value as the longest substring at the current position, and you are done.

Your own answer

There is no

Better Approach (Central extension method)

var longestPalindrome = function(s) {
  function expandString(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      --left
      ++right
    }
    return right - left - 1
  }
  var start = 0
      end = 0
  for (let i = 0; i < s.length; i++) {
    var len1 = expandString(i, i)
        len2 = expandString(i, i + 1)
        len = Math.max(len1, len2)
    if (len > end - start) {
      start = i - ~~((len - 1) / 2)
      end = i + ~~(len / 2)
    }
  }
  return s.substring(start, end + 1)
};
Copy the code

The code is simple. First, it’s an expandString function to extend it. Notice that the return value here is right-left-1, because right and left are extended one more time, so you need to subtract to get the correct length.

The inside of the loop is normal logic, there are two lengths len1 and Len2, the first is very simple, which is to expand from the current position to both sides, and len2 is to expand from the current position to the next position, pretending that the center point is two, and because of the internal logic of the function expandString, if the letters in the two positions are different, Direct GG, don’t worry about this, anyway, just give it a try.

So now I have two lengths, and I take the larger one between them, which is the maximum length of the substring centered on the current position.

The next step is also critical, which determines the start and end of the truncated string.

Actually, it’s a very clever method, and it took me about 10 minutes to understand the essence of this step.

So, when we assign start, we say ~~((len – 1) / 2), why do we do that? So let’s think about the case where len is odd, and in that case, we don’t really need to do this, because we’re rounding down, so 1.5 and 1 are the same thing, so we don’t have to think about it.

What if len is even? Now, this is what’s going to stand out, because if it’s even, when you subtract 1, start is going to quit one less place than end. Why would you do that? Because if it’s even, it means that the center point is two letters, but index starts with the first letter, so the left extension needs to be one less than the right one, so that the number of extensions can be aligned.

Say still may compare psychedelic, the expression ability of the author also stops here, try to bureau.

If you still don’t understand it you can print something and think about whether there’s one center point or two.

Better Way (DP)

To tell the truth, DP did not understand, but I still take JavaScript to translate the official answer, interested students can see 👇 :

var longestPalindrome = function(s) { var len = s.length if (len < 2) return len var maxLen = 1 begin = 0 dp = Array.from({length: len}, () => new Array(len)) for (let i = 0; i < len; i++) { dp[i][i] = true } for (let L = 2; L <= len; L++) { for (let i = 0; i < len; i++) { var j = L + i - 1 if (j >= len) break if (s[i] ! == s[j]) { dp[i][j] = false } else { if (j - i < 3) { dp[i][j] = true } else { dp[i][j] = dp[i + 1][j - 1] } } if (dp[i][j] && j - i + 1 > maxLen) { maxLen = j - i + 1; begin = i } } } return s.substring(begin, begin + maxLen) };Copy the code

A Better Way (Manacher)

This method is the book, see the official answer 👉 : here.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ