WEB后端

当前位置:首页 > 技术世界 > WEB后端

求最长回文子串 - leetcode 5. Longest Palindromic Substring

写在前面:忍不住吐槽几句今天上海的天气,次奥,鞋子里都能养鱼了...裤子也全湿了,衣服也全湿了,关键是这天气还打空调,只能瑟瑟发抖祈祷不要感冒了....

前后切了一百零几道leetcode的题(solution同步在github),主要是拣难度系数定为easy的水题做...好吧,这是第一道算法题。不知哪位大神说的,所有的语言都会过时,只有数据结构和算法才是永恒。

今天要重点讲的是优雅的Manacher算法,先来看这道题Longest Palindromic Substring,题目很简单,给你一个字符串,找到最长的回文子串。啥叫回文串?就是前后看都一样的串,比如abcbaabba,因为题目给的数据量不大(1000),所以可以枚举字符串的每个位置当做回文对称点,回文对称点是我给它的一个概念,比如abcba的回文对称点就是idx=2也就是c的位置。But!并不是每个回文串都有对称点,比如abba,只有对称轴,它就没有点!怎么办?机智的coder想出了一个简单的用空间换取代码实现复杂度的方法,这也是Manacher算法的第一步:

abcba -> #a#b#c#b#a#abba  -> #a#b#b#a#

这么一来,每个回文串就都有回文对称点了(可能是字母,也可能是#)。之后我们就能枚举对称点,然后向两边扩散开去,比较字符是否一样。为了不用判断是否已经到了边界,我们最初在字符串的开头再加个字符*,只要该字符和#以及字符串里其他字符都不一致即可。这样是可以AC的,虽然复杂度达到了O(n^2)。接下去我们介绍复杂度为O(n)的Manacher算法。

我们试着以字符串babcbade举例,首先把字符串像上面一样变形:

babcbade -> *#b#a#b#c#b#a#d#e#

然后我们设置一个dp数组,dp[i]表示以变形后第i个元素为对称点的最长回文子串的半径,同样以上面的字符串举例,可以得到dp数组:

*#b#a#b#c#b#a#d#e#112121216121212121

我们可以很容易地发现,要求的最长回文子串的长度即dp数组最大值减去1。于是如何快速地求得该数组成为关键。假设我们已经得到了dp[6]的值,dp[10]的初始值也不难确定,因为它们两个元素根据idx=8对称(#a#b#c#b#a#),所以可以不用从1开始向两边扩散了。

我们用maxn维护当前存在的回文子串能达到最右的位置+1(maxn位置不可达到),用idx维护当前能到达最右+1的回文子串的回文中心点位置,实现该dp数组求值的核心代码如下:

for (var i = 1, len = str.length; i < len; i++) {  if (maxn > i) dp[i] = Math.min(dp[2 * idx - i], maxn - i);  else dp[i] = 1;  while (str[i - dp[i]] === str[i + dp[i]]) dp[i]++;  if (dp[i] + i > maxn)    maxn = dp[i] + i, idx = i;}

完整的AC代码:

// return the Longest Palindromic Substring of sfunction Manacher(s) {  var str = '*#'    , dp = []    , maxn = 0    , idx = 0;  for (var i = 0, len = s.length; i < len; i++)    str += s[i] + '#';  for (var i = 1, len = str.length; i < len; i++) {    if (maxn > i) dp[i] = Math.min(dp[2 * idx - i], maxn - i);    else dp[i] = 1;    while (str[i - dp[i]] === str[i + dp[i]]) dp[i]++;    if (dp[i] + i > maxn)      maxn = dp[i] + i, idx = i;  }  var ans = 0    , pos;  for (var i = 1; i < len; i++) {    if (dp[i] > ans)      ans = dp[i], pos = i;  }  var f = str[pos] === '#'    , tmp = f ? '' : str[pos]    , startPos = f ? pos + 1 : pos + 2    , endPos = f ? dp[pos] - 3 + startPos : dp[pos] - 4 + startPos;  for (var i = startPos; i <= endPos; i += 2)     tmp = str[i] + tmp + str[i];  return tmp;}var longestPalindrome = function(s) {  var str = Manacher(s);  return str;};

转载说明:欢迎转载本站所有文章,如需转载请注明来源于《绝客部落》。

本文链接:https://juehackr.net/houduan/65.html

相关内容

文章评论

表情

共 0 条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~