专栏首页极客起源算法君带你学算法(1):求最长回文字符串

算法君带你学算法(1):求最长回文字符串

算法君:小白同学,给你出道算法题,看你小子算法能力有没有长进。

算法小白:最近一直在研究算法,刷了很多算法题,正好活动活动大脑,来来来,赶快出题!

算法君:听好了,题目是:求一个字符串中最长的回文字符串。

算法小白:这个算法好像很简单,就是有一个概念不太明白,啥叫“回文字符串”。

算法君:哈哈,你说的很简单,一定是题目的字数很少的意思。

算法小白:哦,又被老大猜中了。还是先给我讲一下什么是回文字符串吧!

算法君:回文字符串吗!首先是一个字符串(废话),然后,核心就是回文。“回”吗,就是来来回回的意思。其实就是正向和反向遍历字符串中的每一个字符,然后嘛,如果遍历的结果都一样,就是回文字符串。例如,有一个字符串abcba,无论正向遍历,还是反向遍历,结果都是abcba,如果还不清楚,可以看下图。

算法小白:太好了,我终于知道什么叫回文字符串了,现在可以做这道题了。只要正向和反向分别遍历一遍字符串,然后比较一下结果,如果两次遍历的结果相同,就是回文字符串,哈哈哈,对吗?老大。

算法君:着什么急,你看清题目了吗?不是让你判断是否为回文字符串,是要在一个字符串中寻找最长回文字符串,例如,akbubk是一个字符串,这里边有很多回文字符串,其实单个字母就是一个回文字符串,还有就是bub、kbubk,很显然,最长的回文字符串就是kbubk。

算法小白:懂了,懂了,题目还要一个条件,就是要找到所有回文字符串中最长的一个。

算法君:真懂了吗? 好吧,说说你怎么设计这个算法。

算法小白:我只用了0.01秒,就想到如何设计了,当然是得到字符串中的所有子串,然后找到所有的回文字符串,最后,当然是对这些回文字符串按长度排序,并找到最大的回文字符串了。哈哈哈,我聪明吗!!!

算法君:Are you crazy?(此时的算法君内心一定是有一万匹草泥马跑过,气得都飙英文了),这么做当然没错,但.....,效率太低了。这要是字符串长点,是要去租用超级计算机运行算法程序吗?

算法小白:不好意思啊,我只想到了这种算法,反正能实现就行呗,管它效率怎样呢!

算法君:设计算法可不光是实现就行,要注重效率、效率、还是效率,重要的事情说三遍。这才能真正体现出算法之美,否则,直接用最笨的方法谁都会。

算法小白:那么老大有什么更好的实现吗?

算法君:当然,我作为老大,自然是肚子里有货了,先给你讲一种效率较高的算法。

算法君:要优化一个算法,首先要知道原来的算法哪里效率低了。就拿前面给出的字符串akbubk来说。u、bub和kbubk都是回文字符串,我们前面说了,判断回文字符串就是要分别正向和反向遍历一遍字符串,然后比较遍历结果,如果结果相同,就是回文字符串。对于单个字符,直接就是回文字符串,对于bub来说,按常规的判断方法,需要正向循环3次(得到正向字符串),反向循环3次(得到反向字符串)。一共6次才能判断该字符串是否为回文字符串(不过正向可以省略了,因为就用字符串本身就可以了),而对于kbubk来说,需要遍历10次才可以。

算法君:这是按常规的做法。但是,我们仔细观察,bub和u的关系,u是包含在bub中的,而且u肯定是回文字符串,所以以u为轴,只要判断该字符串的首字符与尾字符是否相等即可。也就是说,这样一来,就只需要比较一次(首字符和尾字符进行比较)就可以了,效率大大提升。

算法小白:好像是有点明白了。

算法君:别急别急,我还没说完呢!如果感觉bub和u的关系太简单,可以再看一下bub和kbubk的关系。bub是包含在kbubk中的,如果按常规的做法,bub正反遍历两次判断是否为回文字符串,而kbubk同样需要遍历两次,但对于kbubk来说,遍历的这两次,是包含bub的两次遍历的,也就是说,这里重复遍历了。这就是我们应该优化的地方:避免重复遍历字符串。

算法小白:真是醍醐灌顶啊,那么如何避免重复遍历字符串呢?

算法君:当然是保存历史了,我们是怎么知道秦皇汉武、唐宗宋祖的,不就是通过历史书吗?咱们又没见过这几位老哥,对不!

算法小白:保存历史?让我来猜一猜,是不是将已经确认的回文字符串保存起来呢,如果下次再遇到这些已经确认的回文字符串,就不需要再进行遍历了,直接取结果就行了!

算法君:算你小子聪明一回,没错,是要将已经确认的回文字符串保存起来,但并不是保存回文字符串本身。而是要保存字符串是否为回文的结果。还拿kbubk为例,我们可以将kbubk看成3部分,首字符k是一部分,尾字符k是一部分,中间的子字符串bub是一部分,如下图所示。

算法君:对于这个特例来说,bub是回文字符串。而寻找akbubk中最长回文字符串的过程中,肯定是从长度为1的子字符串开始搜索,然后是长度为2的字符串,以此类推,所以bub一定比kbubk先搜索到,所以需要将bub是回文字符串的结果保存起来,如果要判断kbubk是否为回文字符串,只需要经过如下2步就可以了:

1. 判断首尾两个字符是否相同

2. 判断夹在首尾字符中间的子字符串是否为回文字符串

算法君:如果这两步的结果都是yes,那么这个字符串就是回文字符串,将该模型泛化,如下图所示。

算法小白:这下彻底明白了,不过应该如何保存历史呢?设计算法和实现算法还是有一定差别的,这就是理论派和实践派的差距,中间差了一个特斯拉的距离。

算法君:哈哈,理论与实践是有差别的,但好像也没那么大。其实理论与实践很多时候是相辅相成的。

算法小白:快快,给我讲讲到底如何保存历史,给我一架从理论到实践的梯子吧!

算法君:梯子!没有,我这有一壶凉水,浇下去就灌顶了!

算法小白:别逗了,赶快说说!

算法君:要想确定如何保存历史记录,首先要确定如何获取这些数据,然后再根据获取的方式确定具体的数据结构。我们期望知道字符串中任意的子串是否是回文字符串,这个子串的第一个字符在原字符串中的索引是i,最后一个字符在原字符串中的索引是j。所以我们期望有一个函数is_palindrome_string,通过将i和j作为参数传入该函数,如果i和j确定的字符串是回文,返回true,否则返回false。

算法小白:老大的意思是说将i和j作为查询历史记录的key吗?

算法君:没错,这次终于说对了一回。下面就看is_palindrome_string函数如何实现了!

算法小白:我想想啊,那么如何实现这个is_palindrome_string函数呢?通过key搜索是否为回文的历史记录,也就是搜索value,在Python中字典可以实现这个功能。用字典可以吗?

算法君:字典算是一种实现,你想想用字典具体应该如何实现呢?

算法小白:这个我知道,Python我已经很熟悉了。可以将i和j作为一个列表,然后作为字典的key,不不不,该用元组,Python中是不支持将列表作为字典的key的。

例如:history_record = {(1,1):True, (1,3):False}

算法小白:然后通过元组(i,j)查询历史,例如,要想知道索引从1到3的子串是否为回文字符串,只需要搜索history_record即可,代码如下:

history_record[(1,3)]

算法君:没错,这算是一种存储历史的方法,不过搜索字典仍然需要时间,尽管时间不是线性的。想想还有没有更快的定位历史记录的方法呢?

算法小白:快速定位?..... 这个,比字典还快,难道是用魔法吗? 哈哈哈!这个还真一时想不出。

算法君:其实在数据结构中,已经清楚地阐述了最快定位的数据结构,这就是数组,由于数组是在内存中的一块连续空间,所以可以根据偏移量瞬间定位到特定的位置。

算法小白:嗯,数组我当然知道,不过如何用数组来保存回文字符串的历史呢?

算法君:前面提到的is_palindrome_string函数有两个参数i和j。i和j是字符串中某一个字符的索引,从0开始,取值范围都是0 <= i,j < n(这里假设字符串的长度是n),其实这也符合二维数组的索引取值规则。假设有一个n*n的正方形二维数组P(每个元素初始值都是0)。如果从i到j的字符串是回文字符串,那么就将P[i,j]设为1,如果要知道从i到j的字符串是否为回文字符串,也只需要查询P[i,j]即可。

算法君:举个具体的例子,有一个字符串acxxcd,要求该字符串的最大回文字符串,可以创建如下图的6*6的二维数组,初始化为0。

然后将长度为1的字符串标记为回文字符串(主对角线上),如P[0,0],P[1,1]等。

接下来将长度为2 的字符串是回文的做一下标记,也就是两个字符相等的字符串,这里只有一个,那就是xx,也就是P[2,3]。如下图所示。

在字符串acxxcd中,并没有长度为3的回文字符串,所以直接搜索长度为4的回文字符串,如果搜索长度为4的字符串,按着前面的描述,先要判断首尾字符是否相等,如果相等,再判断夹在中间的字符串是否为回文字符串,夹在中间的字符串的长度肯定是2,所以可以直接在这个二维数组上定位。例如,搜索到cxxc,首尾字符都是c,中间的xx在二维数组中的坐标是P[2,3],这个位置刚刚在前面设置为1,所以xx是回文字符串,从而判定cxxc是回文字符串。而cxxc在整个字符串中首尾字符的位置是(1,4),所以需要将P[1,4]设置为1,如下图所示。

继续扫描长度为5的回文字符串(不存在),然后是长度为6的回文字符串(不存在),所以这个唯一的长度为4的回文字符串就是acxxcd的最长回文字符串。

算法君:这种算法还有一个名字:动态规划法。

算法小白:哈哈,还可以这么做。又学了一招!!老大就是老大!

算法君:不过这种存储方案也有缺点,就是比较浪费内存空间,因为需要额外申请n*n的数组空间。另外,你能说出这个算法的时间复杂度和空间复杂度吗?

算法小白:复杂度?我想想,所谓复杂度就是值随着算法输入数据的多少,时间和空间的变化关系吧。如是线性变化的,那么时间复杂度就是O(n)。

算法君:是的,可以这么理解。那么这个算法的复杂度是多少呢?

算法小白:由于该算法需要申请n*n的数组,所以空间复杂度应该是O(n^2),对于每一个字符串,都需要从长度为1的回文字符串开始搜索,需要双重循环,所以时间复杂度也是O(n^2)。

算法君:嗯,这回说得没错,那么还有什么更好的算法可以降低空间复杂度吗?例如,将空间复杂度降为O(1),也就是不需要申请额外的内存空间。

算法小白:我现在已经用脑过度了,这个要回去好好考虑下。感谢老大耐心讲解。

算法君:好吧,回去多想想还有没有更好的算法。如果想知道这些算法的具体实现细节,关注“极客起源”公众号,然后输入229893,即可获得相关资源。除此之外,还有更多精彩内容等着你哦!

#动态规划法求最长回文字符串的完整代码
class MaxPalindromeString:
    def __init__(self):
        self.start_index = None
        self.array_len = None

    def get_longest_palindrome(self,s):
        if s == None:
            return
        size = len(s)

        if size < 1:
            return
        self.start_index = 0
        self.array_len = 1
        # 用于保存历史记录(size * size)
        history_record = [([0] * size) for i in range(size)]

        # 初始化长度为1的回文字符串信息
        i= 0
        while i< size:
            history_record[i][i] = 1
            i += 1

        # 初始化长度为2的回文字符串信息
        i = 0
        while i < size - 1:
            if s[i] == s[i+1]:
                history_record[i][i+1] = 1
                self.start_index = i
                self.array_len = 2
            i += 1

        # 查找从长度为3开始的回文字符串
        p_len = 3
        while p_len <= size:
            i = 0
            while i < size-p_len + 1:
                j = i + p_len-1
                if s[i] == s[j] and history_record[i+1][j-1] == 1:
                    history_record[i][j] = 1
                    self.start_index = i
                    self.array_len = p_len
                i += 1
            p_len += 1
s = 'abcdefgfedxyz'
s1 = 'akbubk'
p = MaxPalindromeString()
p.get_longest_palindrome(s1)

if p.start_index != -1 and p.array_len != -1:
    print('最长回文字符串:',s1[p.start_index:p.start_index + p.array_len])
else:
    print('查找失败')

本文分享自微信公众号 - 极客起源(geekculture),作者:geekori

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-16

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python编程思想(4):字符串类型

    字符串的意思就是“一串字符”,也可以看做是字符的序列。比如“Helo, Mike”是一个字符串,“How are you?”也是一个字符串。Python要求字符...

    蒙娜丽宁
  • Python编程思想(2):Python主要特性、命名规则与代码缩进

    在正式学习Python语言之前,我们先来了解一下Python有哪些特性,以及Python的基本语法结构是怎样的。

    蒙娜丽宁
  • Python的内存管理机制

    任何编程语言都会有一个内存模型,以便管理为变量分配的内存空间。不同的编程语言,如C、C++、Java、C#,Python,它们的内存模型都是不相同的,本文将以现...

    蒙娜丽宁
  • JS实现计算最少回文切割数

    作者注:算法能力一直是程序猿最基础也是最重要的一项基础能力,记得Pascal之父、结构化程序设计的先驱Niklaus Wirth最著名的一本书,书名叫作《算法 ...

    企鹅号小编
  • 20190624一周文章阅读和收藏: 图像分类、检测,NLP,Python编程

    打算每周整理下这周看过觉得不错的文章,主要是机器学习、深度学习、Python编程方向的,包括但不局限于论文、综述、有趣的项目以及工具教程推荐,目前这个系列的名字...

    材ccc
  • SQLServer 学习笔记之超详细基础SQL语句 Part 9

    -----------------------接Part 8-------------------

    授客
  • 入门 | 从原理到应用:简述Logistic回归算法

    机器之心
  • 盘点丨开发者必备:基于 Linux 生态的十大 AI 开源框架

    前不久,AI 科技评论曾盘点了一系列机器学习相关的开源平台,包括谷歌的TensorFlow、微软的CNTK以及百度的PaddlePaddle等等。这些平台各具特...

    AI科技评论
  • 独家 | 手把手教你在试验中修正机器学习模型(附学习资源)

    机器学习的实现路线充满了反复试验。在这个领域,新手工程师和科学家将不断调整他们的算法和模型。此过程中会出现挑战,尤其是在数据处理和确定最优模型的时候。

    数据派THU
  • 一文详解路由算法

    泛泛来讲,网络层在计算机网络中承担的主要功能是:将数据从一台主机移动到另外一台主机。详细一点说,网络层的主要功能是:路由和转发。

    roobtyan

扫码关注云+社区

领取腾讯云代金券