问个回文的算法题，求思路

问个回文的算法题，求思路

回答：

看一眼 Manacher's Algorithm

回答：

一个简单的办法思路：判断数组长度，切一半，取其中一部分，用python 的反转方法，判断前后两端是否一致。

回答：

O(n)的马拉车～

回答：

正解是马拉车，但这个如果面试时写也够呛的哈哈，一个更好理解的算法是通过动态规划。

设 P(i, j) 为 s[i...j] 是否为回文

P(i, i) = true
P(i, i+1) = s[i] === s[i+1]
P(i, j) = P(i+1, j-1) && s[i] == s[j] && i < j

设 len(i, j) 为 s[i...j] 的长度

len(i, j) = j - i + 1

设 LP(i) 为 s[0...i] 中最长回文串的长度

计算 LP(i) 时我们已经有了 LP(i-1)，再跟所有以 s[i] 结尾的回文比较，取最长的即可。

LP(0) = 1
LP(i) = max(LP(i-1), ...len(k, i)), 0 <= k <= i-LP(i-1) && P(k, i) // k 跳过了一些太短的情况

var longestPalindrome = function(s) {
  if (s.length <= 1) {
    return s
  }
  const p = new Array(s.length)
  for (let i = s.length - 1; i >= 0; i--) {
    p[i] = []
    p[i][i] = true
    p[i][i+1] = s[i] === s[i+1]
    for (let j = i + 2; j < s.length; j++) {
      p[i][j] = p[i+1][j-1] && s[i] === s[j]
    }
  }
  let start = 0
  let maxLen = 1
  for (let i = 1; i < s.length; i++) {
    for (let k = 0; k <= i - maxLen; k++) {
      if (p[k][i]) {
        if (i - k + 1 > maxLen) {
          maxLen = i - k + 1
          start = k
        }  
        break
      }
    }
  }
  return s.substr(start, maxLen)
};

回答：

    let s = 'abcdbdbc'
    let getGapMap = str => {
        let temp = {}
        Array.from(str).forEach((item, index) => {
            let gap = index - str.indexOf(item)
            if (gap === 0) return // 间距为 0，不作处理
            temp[gap] = temp[gap] || []
            temp[gap].push(item)
        })
        return temp
    }
    let gapMap = getGapMap(s)
    let maxGap = Math.max(...Object.keys(gapMap))
    let result = gapMap[maxGap].map(item => {
        return s.substr(s.indexOf(item), maxGap)
    })
    console.log(result) // ["bcdbd", "cdbdb"]

以上是 问个回文的算法题，求思路 的全部内容， 来源链接： utcz.com/a/161400.html

回到顶部