回文
利用 python 自带的翻转 函数 reversed()
- def is_plalindrome(string):
- return string == ''.join(list(reversed(string)))
自己实现
- def is_plalindrome(string):
- string = list(string)
- length = len(string)
- left = 0
- right = length - 1
- while left <right:
- if string[left] != string[right]:
- return False
- left += 1
- right -= 1
- return True
当然还有切片 string[::-1]
最长的回文子串
暴力破解
暴力破解, 枚举所有的子串, 对每个子串判断是否为回文, 时间复杂度为 O(n^3)
动态规划
- def solution(s):
- s = list(s)
- l = len(s)
- dp = [[0] * l for i in range(l)]
- for i in range(l):
- dp[i][i] = True
- # 当 k = 2 时要用到
- dp[i][i - 1] = True
- resLeft = 0
- resRight = 0
- # 枚举子串的长度
- for k in range(2, l+1):
- # 子串的起始位置
- for i in range(0, l-k+1):
- j = i + k - 1
- if s[i] == s[j] and dp[i + 1][j - 1]:
- dp[i][j] = True
- # 保存最长的回文起点和终点
- if resRight - resLeft + 1 < k:
- resLeft = i
- resRight = j
- return ''.join(s[resLeft:resRight+1])
时间复杂度为 O(n^2), 空间复杂度为 O(n^2)
Manacher 算法
Manacher 算法首先对字符串做一个预处理, 使得所有的串都是奇数长度, 插入的是同样的符号且符号不存在与原串中, 串的回文性不受影响
- aba => #a#b#a#
- abab => #a#b#a#b#
我们把回文串中最右位置与其对称轴的距离称为回文半径, Manacher 算法定义了一个回文半径数组 RL,RL[i] 表示以第 i 个字符为对称轴的回文半径, 对于上面得到的插入分隔符的串来说, 我们可以得到 RL 数组
- char: # a # b # a #
- RL: 1 2 1 4 1 2 1
- RL-1: 0 1 0 3 0 1 0
- i: 0 1 2 3 4 5 6
- char: # a # b # a # b #
- RL: 1 2 1 4 1 4 1 2 1
- RL-1: 0 1 0 3 0 3 0 1 0
- i: 0 1 2 3 4 5 6 7 8
我们还求了 RL[i] - 1: 我们发现 RL[i] -1 正好是初始字符串中以位置 i 为对称轴的最长回文长度
所以下面就是重点如何求得 RL 数组了, 可以参考这篇文章 (讲得比较清晰)
下面是算法实现
- def manacher(preS):
- s = '#' + '#'.join(preS) + '#'
- l = len(s)
- RL = [0] * l
- maxRight = pos = maxLen = 0
- for i in range(l):
- if i <maxRight:
- RL[i] = min(RL[2*pos - i], maxRight-i)
- else:
- RL[i] = 1
- while i - RL[i]>= 0 and i + RL[i] <l and s[i - RL[i]] == s[i + RL[i]]:
- RL[i] += 1
- if i + RL[i] - 1> maxRight:
- maxRight = i + RL[i] - 1
- pos = i
- maxLen = max(RL)
- idx = RL.index(maxLen)
- sub = s[idx - maxLen + 1: idx + maxLen]
- return sub.replace('#', '')
空间复杂度: 借助了一个辅助数组, 空间复杂度为 O(n) 时间复杂度: 尽管内层存在循环, 但是内层循环只对尚未匹配的部分进行, 对于每一个字符来说, 只会进行一次, 所以时间复杂度是 O(n)
最长回文前缀
所谓前缀, 就是以第一个字符开始
下面的最长回文前缀
- abbabbc => abbc
- abababb => ababa
- sogou => s
将原串逆转, 那么问题就转变为求原串的前缀和逆串后缀相等且长度最大的值, 这个问题其实就是 KMP 算法 http://youbookee.com/2016/09/18/kmp-python/ 中的 next 数组的求解了
具体求解: 将原串逆转并拼接到原串中, 以'#' 分隔原串和逆转避免内部字符串干扰.
- def longest_palindrome_prefix(s):
- if not s:
- return 0
- s = s + '#' + s[::-1] + '$'
- i = 0
- j = -1
- nt = [0] * len(s)
- nt[0] = -1
- while i <len(s) - 1:
- if j == -1 or s[i] == s[j]:
- i += 1
- j += 1
- nt[i] = j
- else:
- j = nt[j]
- return nt[len(s) - 1]
添加字符生成最短回文字符串
这道题其实跟上面基本是一样的, 实例:
- aacecaaa -> aaacecaaa # 添加 a
- abcd -> dcbabcd # 添加 dcb
我们先求字符串的最长回文前缀, 然后剩余的字符串逆转并拼接到字符串的头部即是问题所求
- def solution(s):
- length = longest_palindrome_prefix(s)
- return s[length:][::-1] + s
最长回文子序列
动态规划法
dp[i][j] 表示子序列 s[i..j] 中存在的最长回文子序列长度
初始化 dp[i][i] = 1
当 s[i] == s[j] 为 true 时, dp[i][j] = dp[i+1][j - 1] + 2
当 s[i] == s[j] 为 false 时, dp[i][j] = max(dp[i+1][j], dp[i][j - 1])
- # 求得最长回文子序列的长度
- def solution(s):
- l = len(s)
- dp = [[0] * l for i in range(l)]
- for i in range(l):
- dp[i][i] = 1
- # 枚举子串的长度
- for k in range(2, l+1):
- # 枚举子串的起始位置
- for i in range(0, l-k+1):
- j = i + k - 1
- if s[i] == s[j]:
- dp[i][j] = dp[i + 1][j - 1] + 2
- else:
- dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
- return dp[0][l-1]
时间复杂度为 O(n^2), 空间复杂度为 O(n^2)
转自:
来源: https://juejin.im/entry/5beaf63e6fb9a04a0f64b823