动态规划，中心扩散：求解《647. 回文子串》和《5. 最长回文子串》

动态规划，递归和迭代两种方式中心扩散，求解《647. 回文子串》和《5. 最长回文子串》

子串

• 连续
• 子字符串

代码模板

动态规划

const n = s.length
for (let l = 0; l < n; l++) {
  for (let i = 0; i + l < n; i++) {
    const j = i + l
    if (l === 0) dp[i][j] = 1
    else if (l === 1) dp[i][j] = s[i] === s[j] ? 1 : 0
    else dp[i][j] = s[i] === s[j] ? dp[i + 1][j - 1] : 0 
  }
}

中心扩散 · 递归版

const n = s.length
const d = i => {
  spread(i, i)
  spread(i, i + 1)
  if (i + 1 < n) d(i + 1)
}
const spread = (l, r) => {
  while (l >= 0 && r < n && s[l] === s[r]) {
    l--
    r++
  }
  const len = r - l - 2 + 1 // 长度
}

中心扩散 · 迭代版

aba 共 a b a ab ba *2n - 1** 个中心点

const n = s.length
for (let i = 0; i < 2 * n - 1; i++) {<br>  let l = i >> 1
  let r = (i + 1) >> 1
  while (l >= 0 && r < n && s[l] === s[r]) {
     l++
     r--
  }
  const len = r - l - 2 + 1 // 长度
}

例题

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

答案

动态规划

var countSubstrings = function(s) {
  const n = s.length, dp = Array.from({length : n}, _ => new Uint8Array(n))
  let r = 0
  for (let l = 0; l < n; l++) {
    for (let i = 0; i + l < n; i++) {
      const j = i + l
      if (l === 0) dp[i][j] = 1
      else if (l === 1) dp[i][j] = s[i] == s[j] ? 1 : 0
      else dp[i][j] = s[i] === s[j] ? dp[i + 1][j - 1] : 0
      if (dp[i][j] === 1) r++
    }
  }
  return r
};

func countSubstrings(s string) int {
  n := len(s)
  dp := make([][]int, n)
  for i := 0; i < n; i++ {
    dp[i] = make([]int, n)
  }
  r := 0
  for l := 0; l < n; l++ {
    for i := 0; i + l < n; i++ {
      j := i + l
      if l == 0 {
        dp[i][j] = 1
      } else if (l == 1) {
        if s[i] == s[j] {
          dp[i][j] = 1
        } else {
          dp[i][j] = 0
        }
      } else {
        if s[i] == s[j] {
          dp[i][j] = dp[i + 1][j - 1]
        } else {
          dp[i][j] = 0
        }
      }
      if dp[i][j] == 1 {
        r++
      }
    }
  }
  return r
}

中心扩散 · 递归版

var countSubstrings = function(s) {
  const n = s.length
  const d = i => {
    spread(i, i)
    spread(i, i + 1)
    if (i + 1 < n) d(i + 1)
  }
  let ans = 0
  const spread = (l, r) => {
    while (l >= 0 && r < n && s[l] === s[r]) {
      l--
      r++
      ans++
    }
  }
  d(0)
  return ans
};

func countSubstrings(s string) int {
  n := len(s)
  ans := 0
  var spread func (l int, r int)
  spread = func (l int, r int) {
    for l >= 0 && r < n && s[l] == s[r] {
      l--
      r++
      ans++
    }
  }
  var d func (i int)
  d = func (i int) {
    spread(i, i)
    spread(i, i + 1)
    if i + 1 < n {
      d(i + 1)
    }
  }
  d(0)
  return ans
}

中心扩散 · 迭代版

var countSubstrings = function(s) {
  const n = s.length
  let ans = 0
  for (let i = 0; i < 2 * n - 1; i++) {
    let l = i >> 1
    let r = (i + 1) >> 1
    while (l >= 0 && r < n && s[l] === s[r]) {
      l--
      r++
      ans++
    }
  }
  return ans
};

func countSubstrings(s string) int {
  n := len(s)
  ans := 0
  for i := 0; i < n * 2 - 1; i++ {
    l := i / 2
    r := (i + 1) / 2
    for l >= 0 && r < n && s[l] == s[r] {
      l--
      r++
      ans++
    }
  }
  return ans
}

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

答案

动态规划

var longestPalindrome = function(s) {
  const n = s.length, dp = Array.from({length: n}, _ => new Uint8Array(n))
  let r = ''
  for (let l = 0; l < n; l++) {
    for (let i = 0; i + l < n; i++) {
      const j = i + l
      if (l === 0) dp[i][j] = 1
      else if (l === 1) dp[i][j] = s[i] === s[j] ? 1 : 0
      else dp[i][j] = s[i] === s[j] ? dp[i + 1][j - 1] : 0
      if (dp[i][j] && l + 1 > r.length) r = s.substring(i, j + 1)
    }
  }
  return r
};

func longestPalindrome(s string) string {
  n := len(s)
  dp := make([][]int, n)
  for i := 0; i < n; i++ {
    dp[i] = make([]int, n)
  }
  r := ""
  for l := 0; l < n; l++ {
    for i := 0; i + l < n; i++ {
      j := i + l
      if l == 0 {
        dp[i][j] = 1
      } else if l == 1 {
        if s[i] == s[j] {
          dp[i][j] = 1
        } else {
          dp[i][j] = 0
        }
      } else {
        if s[i] == s[j] {
          dp[i][j] = dp[i + 1][j - 1]
        } else {
          dp[i][j] = 0
        }
      }
      if dp[i][j] == 1 && l + 1 > len(r) {
        r = s[i:j + 1]
      }
    }
  }
  return r
}

中心扩散 · 递归版

var longestPalindrome = function(s) {
    let ans = ''
    const n = s.length
    const d = i => {
      spread(i, i + 1)
      spread(i - 1, i + 1)
      if (i + 1 < n) d(i + 1)
    }
    const spread = (l, r) => {
      while (l >= 0 && r < n && s[l] === s[r]) {
        l--
        r++
      }
      if (r - l - 2 + 1 > ans.length) ans = s.substring(l + 1, r)
    }
    d(0)
    return ans
};

var ans string
func longestPalindrome(s string) string {
  ans = ""
  d(0, s)
  return ans
}
func d(i int, s string) {
  spread(i, i + 1, s)
  spread(i - 1, i + 1, s)
  if i + 1 < len(s) {
    d(i + 1, s)
  }
}
func spread(l int, r int, s string) {
  for l >= 0 && r < len(s) && s[l] == s[r] {
    l--
    r++
  }
  if r - l - 2 + 1 > len(ans) {
    ans = s[l + 1 : r]
  }
}

中心扩散 · 迭代版

var longestPalindrome = function(s) {
  const n = s.length
  let ans = ''
  for (let i = 0; i < n * 2 - 1; i++) {
    let l = i >> 1
    let r = i + 1 >> 1
    while (l >= 0 && r < n && s[l] === s[r]) {
      l--
      r++
    }
    if (r - l - 2 + 1 > ans.length) ans = s.substring(l + 1, r)
  }
  return ans
};

func longestPalindrome(s string) string {
  n := len(s)
  ans := ""
  for i := 0; i < n * 2 - 1; i++ {
    l := i / 2
    r := (i + 1) / 2
    for l >= 0 && r < n && s[l] == s[r] {
      l--
      r++
    }
    if r - l - 2 + 1 > len(ans) {
      ans = s[l + 1 : r]
    }
  }
  return ans
}