Topic:

Given a string s, find the longest subroutine in s. You can assume that the maximum length of s is 1000. Example 1: Input: “babad” Output: “bab” Note: “ABA” is also a valid answer.

Example 2: Input: “CBBD” Output: “bb”

When I first came into contact with this problem, MY own idea was whether the stack could be used to match the value of the top element of the stack with that of the next element. After I tried, I found that it was not possible. Because IT’s hard for me to tell which element in the stack matches, say, badac string

After the last letter a is pressed, it is not known which letter to pop.

Explain this method I can not solve, later saw others to solve the problem, learn and then digest, now to sum up the problem solving ideas

Let’s look at the core code first

func isCharacterMatch(left int, right int, str string, max *int, st *int) {
 for {
  if left >= 0 && right < len(str) && str[left] == str[right]{
   if right - left + 1 > *max{
    *max = right - left + 1
 *st = left  }  left = left - 1  right = right + 1  }else{  break  }  } } Copy the code

The core of this method is the three judgment conditions in if

  1. left>=0
  2. right < len(str)
  3. str[left] == str[right]\

And then let’s take an example and explain how these three conditions can be satisfied so let’s think about two examples,

  1. babad
  2. cabbae

Is there anything special about these two examples? There is a difference in where the string starts from the center, so let’s draw a picture

The two centers of a string are different

In other words, there are two conditions that we need to do

The first one is I minus one, I plus one.

The second one is I, I +1.

Let’s say I is equal to 1

So that’s it, and then we go to the next if, why is this if plus 1?

Let’s look at another picture

So what’s Max here?

Max is actually the length of the longest palindrome string currently found

So we need to update the longest palindrome string if we find it longer than the current one

Namely \

*max = right - left +1
*st = left
Copy the code

In this line st is the position of the string start. Let’s look at another picture \

So the answer to this question is bab (of course ABA also works)

Now that we’ve done the first example, let’s look at the second example of Cabbad

Same idea, we can’t do that in example 2

Because in this case, I and I +1 are the center points and then spread out to both sides,

Then let’s look inside the if at the bottom layer


So, we’ve explained the core of this, so to sum it up

Then we look at the main function \

func longestPalindrome(s string) string {
 if len(s) < 2{
  return s
 }
  maxLength  := 0
 start := 0  for i := 0; i< len(s); i++{  isCharacterMatch(i, i+1, s, &maxLength, &start)  isCharacterMatch(i- 1, i+1, s, &maxLength, &start)   }  fmt.Println(start, maxLength)  if start ==0 && maxLength ==0 {  return string(s[0])  }  str := s[start:start+maxLength]  return str } Copy the code

The for in the main function is just to iterate through the string, and then, If len(s)<2, for example, a -> its palindrome is itself. If ab->a refers to elements of STR [0]. Finally, we return start -> start+maxLength, Is the largest palindrome string \

Record your own understanding process and are not familiar with GoLan. Let’s work together!