算法君: 小白同学, 给你出道算法题, 看你小子算法能力有没有长进.
算法小白: 最近一直在研究算法, 刷了很多算法题, 正好活动活动大脑, 来来来, 赶快出题!
算法君: 听好了, 题目是: 求一个字符串中最长的回文字符串.
算法小白: 这个算法好像很简单, 就是有一个概念不太明白, 啥叫 "回文字符串".
算法君: 哈哈, 你说的很简单, 一定是题目的字数很少的意思.
算法小白: 哦, 又被老大猜中了. 还是先给我讲一下什么是回文字符串吧!
算法君: 回文字符串吗! 首先是一个字符串(废话), 然后, 核心就是回文."回" 吗, 就是来来回回的意思. 其实就是正向和反向遍历字符串中的每一个字符, 然后嘛, 如果遍历的结果都一样, 就是回文字符串. 例如, 有一个字符串 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), 也就是不需要申请额外的内存空间.
算法小白: 我现在已经用脑过度了, 这个要回去好好考虑下. 感谢老大耐心讲解.
算法君: 好吧, 回去多想想还有没有更好的算法. 下面给出一个具体的算法实现(Python 语言).
- # 动态规划法求最长回文字符串的完整代码
- 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('查找失败')
来源: https://www.cnblogs.com/nokiaguy/p/12091547.html