Topic describes
Longest string of subroutines
Given a string s, find the longest substring in s.
Example 1:
Enter: s ="babad"Output:"bab"Explanation:"aba"It is also the answer to the question. The sample2: Enter: s ="cbbd"Output:"bb"
Copy the codeRelated topics: Longest sequence of rhymes
Solution a:
Violent matching, starting from scratch, is O(n3).
Method 2:
The greedy solution, we think that the length of the answer string is the length of the entire string, and then we match it in the string based on that length. The time is also O(n3). But since the first string is the answer, it’s a little bit faster than the first one.
Method 3:
We assume a string center (which could be X or XX) and then spread out along the center to find the longest sequence of subroutines centered on this character (or two). It’s down to O(n2).
Why does it have the effect of reducing complexity? This is because we use a string that is already a subroutine sequence to find a longer string. This is a good way to approach a problem: use substates/subquestion answers to expand the search for answers.
class Solution {
  public String longestPalindrome(String s) {
    int ansIndex = 0, max = 0, pl = 0;
    boolean isEven = false;
    for (int i = 0; i < s.length(); i++) {
      pl = 0;
      for(int j = 0; j + i < s.length() && i - j >= 0; j++) {
        if(s.charAt(j + i) == s.charAt(i - j)) pl++;
        else break;
     }
      if(max < pl * 2 -1) {
        max = pl * 2 - 1; ansIndex = i; }}// To optimize a bit, you can actually start with Max /2
    for (int i = max / 2; i < s.length() - 1; i++) {
      if(s.charAt(i) == s.charAt(i + 1)) {
        pl = 1;
        for(int j = 1; i + j  + 1 < s.length() && i - j >= 0; j++) {
          if(s.charAt(j + i + 1) == s.charAt(i - j)) pl++;
          else break;
       }
        if(max < pl * 2) {
          max = pl * 2;
          ansIndex = i;
          isEven = true; }}}if(isEven) {
      return s.substring(ansIndex - max / 2 + 1, ansIndex + max / 2 + 1);
   } else {
      return  s.substring(ansIndex - (max + 1) / 2 + 1, ansIndex + (max + 1) / 2); }}}Copy the codeYou can actually optimize this a little bit. Let’s make solution three sum with the greedy algorithm, so we go from having the diffusion center on the far left, to having the diffusion center on the far right. This gives us a better chance of getting a longer sequence of subroutines. (The above writing method can achieve both time efficiency and space efficiency of more than 80% in Leetcode, which can be better after optimization.)
Method 4:
Dynamic programming, which is a more general way of writing an extended search for an answer using substate/subquestion answers. We get the following dynamic programming formula: Dp [I] [j] = {dp + 1] [I [j – 1) + 2 s = s [j] [I] 0 s [j] [I] indicates s dp [j] = \ [I] the begin {cases} dp + 1] [I] [j – 1 + 2 & s [j] [I] = s \ \ & s \ [I] 0 ne s [j]. Dp \ end {cases} [I] [j] = {dp + 1] [I [j – 1) + 20 s = s [j] [I] [I] î€ s = s [j] which s is a string. Notice the boundary conditions.
But this kind of dynamic programming is not really necessary, because it wastes more space than solution three but has the same time complexity. But we can get a deeper understanding of the core idea of dynamic programming through this solution.
Method 5:
Manacher algorithm, specifically to solve the subpalindrome string algorithm of such strings.
Its core idea is to try to use known conditions to reduce the subsequent difficulty. The process of the algorithm is more complicated, and the graph is a little abstract. You can learn about it yourself if you are interested.
Here gives the code (Java code, js,ts,c++ code partners can leave a message to me) :
class Solution {
  public String longestPalindrome(String s) {
    char[] str = new char[s.length() * 2 + 1];
    // fill STR to make it an odd number
    for(int i = 0; i < s.length() * 2 + 1; i++) {
      if (i % 2= =1) {
        str[i] = s.charAt(i / 2);
     } else {
        str[i] = The '#'; }}int[] f = new int[str.length];
    int  r = 0, index = 0;
    for (int i = 1; i < str.length; i++) {
      // If the current location is at the edge of the previous exploration, you need to expand out from that location
      if(i >= r) {
        f[i] = (int) extend(i, 0, str);
        index = i;
        r = i + f[i];
     }
      else {
        // Perform different operations depending on the mirroring situation
        final int mir = index - (i - index);
        if(mir - f[mir] > index - f[index]) f[i] = f[index - (i - index)];
        else if(mir - f[mir] == index - f[index]) {
          f[i] = (int) extend(i, f[mir], str);
          index = i;
          r = i + f[i];
       }
        else f[i] = mir - (index - f[index]);
     }
   }
    String ans = "";
    int ansNum = 0, ansIndex = 0;
    for(int i = 0; i < f.length; i++) {
      if(ansNum < f[i]) { ansNum = f[i]; ansIndex = i; }}for (int i = ansIndex - ansNum; i <= ansIndex + ansNum; i++) {
      ans = ans + str[i];
   }
    return  ans.replace("#"."");
 }
​
  / * * * *@paramPindex Current position *@paramRadius matches from the radius of this location *@returnReturn the new r */
  public Number extend(int pindex,int radius,char[] str) {
    radius++;
    while(pindex + radius < str.length && pindex - radius >= 0) {
      if(str[pindex + radius] == str[pindex - radius]) radius ++;
      else break;
   }
    return  radius - 1; }}Copy the codeThe advantage of the horse-drawn cart algorithm is that it makes full use of the characters that have already been matched. In the above code, the overall algorithm complexity is reduced to O(N) because r(the maximum distance to the right) is not repeated in the extension, and the time consumption is O(1) except for the time consumption caused by the extension of R.