The title

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
  • sConsists of only numbers and English letters (uppercase and/or lowercase)

recursive

According to the properties of a palindrome string, you can compare layers from the outside to the inside, and as long as you find any layer of characters are not equal, you can determine that this is not a palindrome string.

We can save only the left and right indexes of the substring and retrieve them from the string when we return.

function longestPalindrome(s: string) :string {
  const n = s.length
  const helper = (i: number.j: number) :boolean= > {
    if (i === j) return true
    if(s[i] ! == s[j])return false
    if (i + 1 === j) return true

    return helper(i + 1, j - 1)}let [left, right] = [0.1]
  for (let i = 0; i < n - 1; i++) {
    for (let j = n - 1; j > i; j--) {
      if (helper(i, j) && j - i + 1 > right - left) [left, right] = [i, j + 1]}}return s.slice(left, right)
}
Copy the code
  • Time complexity: O(n3)O(n^3)O(n3)
  • Space complexity: O(n)O(n)O(n)

Memorization recursion

The complexity of the direct recursion is O(n3)O(n^3)O(n3), and we can optimize the time complexity within the recursion by adding caching

function longestPalindrome(s: string) :string {
  const n = s.length
  const cache: boolean[] [] =new Array(n).fill(0).map(() = > [])
  const helper = (i: number.j: number) :boolean= > {
    if(cache[i][j] ! = =undefined) return cache[i][j]

    if (i === j) return true
    if(s[i] ! == s[j])return false
    if (i + 1 === j) return true

    cache[i][j] = helper(i + 1, j - 1)
    return cache[i][j]
  }
  let [left, right] = [0.1]
  for (let i = 0; i < n - 1; i++) {
    for (let j = n - 1; j > i; j--) {
      if (helper(i, j) && j - i + 1 > right - left) [left, right] = [i, j + 1]}}return s.slice(left, right)
}
Copy the code
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n2)O(n^2)O(n2)

Dynamic programming

Convert the mnemonization recursion above into dynamic programming

Point to note is the direction of the traversal, recursive, the call stack to help us save the information, so we can be invoked from outside to inside layers, then layers in from the back, and when using the dynamic programming, requires from the inside first, and then according to the status of inside outside to determine its own state. There are two ways to traverse, either from back to front or from front to back, where j only needs to traverse up to I, and the other side is completely symmetric.

We choose to go from front to back, I from 0 to S. Length,j from 0 to I.

  • Status:dp[i][j]Said substrings[j..i]Is it a palindrome
  • Transfer equation:
    • dp[i][j] = s[i]===s[j] && dp[i-1][j+1]
  • Boundary:
    • dp[i][i]=trueA single character is a subroutine
    • There will be a special case, for examplecbbdWhen I =2 and j=1, both b are equal, butdp[i-1][j+1]It’s undefined, so the transfer equation above will return false, but in factbbBut it does meet the requirements of a substring, so it needs special treatment, which we use here??Reset undefined to true
function longestPalindrome(s: string) :string {
  const n = s.length
  let [left, right] = [0.1]
  const dp: boolean[] [] =new Array(n).fill(0).map(() = > [])
  for (let i = 0; i < n; i++) {
    dp[i][i] = true
    for (let j = 0; j < i; j++) {
      dp[i][j] = s[i] === s[j] ? dp[i - 1]? .[j +1]????true : false
      if (dp[i][j] && i - j + 1 > right - left) [left, right] = [j, i + 1]}}return s.slice(left, right)
}
Copy the code
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n2)O(n^2)O(n2)

To optimize the

By studying the transition equation, only the true state will be transferred, so it is not necessary to traverse j from 0 to I, but to save the previous true state, and then to judge whether S [I] is equal to s[j] by traversing the true state, which will be faster. Of course, if you encounter some extreme cases, you still need to go through them all, such as the string aaaaAAaaaa with all a’s.

Another such traversal, can’t get the variable j, whether the state can not only save for Boolean value, like back to the text string and need deposit can let us find need to compare the value of j, here you can choose to save and the current characters back to the other side of the text string index, or deposit back text can also be the length of the string, both can get j through calculation The information. The corresponding index is saved in the following code.

function longestPalindrome(s: string) :string {
  const n = s.length
  let [left, right] = [0.1]
  const dp: number[] [] =new Array(n).fill(0).map(() = > [])
  for (let i = 0; i < n; i++) {
    dp[i].push(i)
    dp[i].push(i + 1)

    // if (s[i] === s[i - 1]) {
    // dp[i].push(i - 1)
    / /; [left, right] = [i - 1, i + 1]
    // }
    // The above code is needed to do extra processing for examples like 'CBBD'
    // However, 'dp[I].push(I + 1)' saves extra code and integrates directly into the loop below

    for (const j of dp[i - 1]???? []) {if (s[i] === s[j - 1]) {
        dp[i].push(j - 1)
        if (i - j + 2 > right - left) [left, right] = [j - 1, i + 1]}}}return s.slice(left, right)
}
Copy the code
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n2)O(n^2)O(n2)

Space optimization

In the dynamic programming above, each time the state of I is only related to i-1, so it can be spatially optimized to use two one-dimensional arrays to store the state

function longestPalindrome(s: string) :string {
  const n = s.length
  let [left, right] = [0.1]
  let pre: number[] = []
  let cur: number[] = [0.1]
  for (let i = 0; i < n; i++) {
    for (const j of pre) {
      if (s[i] === s[j - 1]) {
        cur.push(j - 1)
        if (i - j + 2 > right - left) [left, right] = [j - 1, i + 1]}}; [cur, pre] = [[i +1, i + 2], cur]
  }

  return s.slice(left, right)
}
Copy the code
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n)O(n)O(n)

The purpose of this article is to study how to move from mnemonic search to dynamic programming. There are other solutions to this problem, such as the central extension algorithm, and the better O(n)O(n)O Manacher algorithm. Those who are interested can check out the official problem solving section as well as other problem solving sections.