Python实现常见的回文字符串算法

回文

利用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 算法中的 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

最长回文子序列

动态规划法

  1. dp[i][j] 表示子序列 s[i..j] 中存在的最长回文子序列长度
  2. 初始化dp[i][i] = 1
  3. 当 s[i] == s[j] 为 true 时,dp[i][j] = dp[i+1][j - 1] + 2
  4. 当 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)

转自:http://youbookee.com/2016/09/06/plalindrome-substring/

原文发布于微信公众号 - Python爬虫与算法进阶(zhangslob)

原文发表时间:2018-11-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

从零开始学算法:高精度计算

前言:由于计算机运算是有模运算,数据范围的表示有一定限制,如整型int(C++中int 与long相同)表达范围是(-2^31~2^31-1),unsigned...

372130
来自专栏拭心的安卓进阶之路

Java 集合深入理解(16):HashMap 主要特点和关键方法源码解读

前面我们介绍了 哈希相关概念:哈希 哈希函数 冲突解决 哈希表,这篇文章我们来根据 JDK 1.8 源码,深入了解下使用频率很高的 HashMap 。 读完本...

29950
来自专栏移动开发面面观

OpenGL ES——着色器

16020
来自专栏前端杂谈

前端算法-基本排序算法比较

383130
来自专栏Python小屋

Python内置函数int()高级用法

int()函数常用来把其他类型转换为整数,例如: >>> int(3.2) 3 >>> int(1/3) 0 其实,int是Python内置类型之一,之所以能...

31470
来自专栏小詹同学

Leetcode打卡 | No.015 三数之和

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

14920
来自专栏CDA数据分析师

学会这8个(组)excel函数,轻松解决工作中80%的难题

文 | 兰色幻想-赵志东 函数是excel中最重要的分析工具,面对400多个excel函数新手应该从哪里入手呢?下面是实际工作中最常用的8个(组)函数,学会后工...

21070
来自专栏数据结构与算法

P1410 子序列

题目描述 给定一个长度为N(N为偶数)的序列,问能否将其划分为两个长度为N/2的严格递增子序列, 输入输出格式 输入格式: 若干行,每行表示一组数据。对于每组数...

28260
来自专栏海天一树

小朋友学算法(6):求幂pow函数的四种实现方式

在math.h中,声明了一个函数pow(x, n),用于求x的n次方。 假如咱们不调用math.h中的pow函数,如何实现求x ^ n的算法呢?

22220
来自专栏C/C++基础

华为2017校招C++岗笔试题

输入两个字符串M和N,从字符串M中删除字符串N中所有的字符。例如,输入”abcda”和”ac”,则删除之后的第一个字符串变成”bd”。

68710

扫码关注云+社区

领取腾讯云代金券