Menu Close

动态规划解最长子序列子串等一类问题之让字符串成为回文及其Follow Up[Sika Deer]

这是个好题目

pexels-photo-219906.jpeg

0.源起

1589122737432.png

1.Step1

源问题,如上图,让字符串成为回文串的最少插入次数

定义状态

  • nstr的长度,dp[n][n]是一张二维表
  • 定义:dp[i][j]表示的是子串str[i][j]最少添加多少字符可以使其整体变成一个回文,注意,是最少
  • 要求的结果是dp[0][n-1]表示的是str[0...n-1]也就是这个字符从开头到结尾,要想形成回文,最少的添加字符的个数

问题来了,如何填写这张dp table呢?

  • 分三大类讨论
  • 1.str[i...j]只有一个字符,即i==j,如图,str[i...j]=A,一个字符要形成回文,很简单,不要向其增加字符,即其本身可以形成回文,即dp[i][j]=0
  • 2.str[i...j]有两个字符
    • 2.1,当str[i]==str[j],即两个字符相同时,其与场景1的情况一样,例如,AA不需要添加字符,即可使其成为回文,即dp[i][j]=0
    • 2.2,当str[i]!=str[j],即两个字符不同时,例如,AB,可以在前面加一个B,变成BAB,也可以在后面加一个A,变成ABA,总之是只要添加一个字符,即可使其变成回文,即dp[i][j]=1
  • 3.str[i...j]有三个或者三个以上字符,这就属于一般的情况了
    • 3.1.当str[i]==str[j]时,例如,ABDCA,只需要考虑BDC,也即要求dp[i][j],转化为求dp[i+1][j-1],只要搞定str[i+1...j-1]部分,使其变成回文,再加上str[i]str[j],整体就变成回文了,即转移方程:dp[i][j]=dp[i+1][j-1]
    • 3.2.当str[i]!=str[j]时,有两种方法使其变成回文,一种是先让str[i...j-1]变成回文,在i的左边添加str[j],整体就会变成回文,例如ABECD,可以先考虑ABEC这部分,一个方案是ABECEBA,再在ABECEBA左边加上str[j],即D,带上源字符的D,变成了DABECEBAD;另外一种方案,同理,先让str[i+1...j]变成回文,最后在右边加上str[i],最终变成了整体回文,那么,动态转移方程式什么呢?
    • 要想使str[i...j-1]变成回文,其最少的添加次数是dp[i][j-1],再加上往左侧补的字符,最终应该是dp[i][j-1]+1
    • 同理可得,dp[i+1][j]+1
    • dp[i][j]=min(dp[i][j-1],dp[i+1][j])+1

Package Diagram.jpg

核心代码

  • 生成dp table的代码,注意遍历时,综合考虑了以上分析的三种情况
  • 下文中需要使用到这个buildDP,做个一个抽离

整体代码

复杂度分析

  • 时间复杂度:O(N^2)N是字符的长度
  • 空间复杂度:O(N^2)dp表的空间

2.Step2

题目

给定一个字符串str,如果可以在str的任意位置添加字符,请返回在添加字符最少的情况下,让str整体都是回文字符串的结果。

  • 这个问题比Step1的问题多了一步,要求返回一种使其变成整体回文的结果,例如,源字符AB,返回一种添加最少字符,使其变成回文的一种方案,返回ABA或者BAB均可

解题思路

  • 准备一个res数组,长度是字符s本身的长度+dp[0][n-1]
  • 运用双指针的想法,给res填充字符
    • str[i]==str[j]时,res直接追加即可
    • str[i]!=str[j]时,需要找到一个最少添加字符的方案
    • dp[i][j - 1] < dp[i + 1][j]时,即最终在生成字符的时候,在左侧填充一个str[j]
    • dp[i][j - 1] >= dp[i + 1][j]时,即最终在生成字符的时候,在右侧填充一个str[i]

整体代码

复杂度分析

  • 时间复杂度:O(N^2)N是字符的长度,求res的过程是O(N),总体是O(N^2)
  • 空间复杂度:O(N^2)dp表的空间

3.Step3

给定一个字符串str,再给定str的最长回文子序列字符串strlps,请返回在添加字符最少的情况下,让str整体都是回文字符串的一种结果。进阶问题比原问题多了一个参数,请做到时间复杂度比原问题的实现低

举例:

str="A1B21C",strlps="121",返回"AC1B2B1CA"或者"CA1B2B1AC",总之,只要是添加的字符数最少,只返回其中一种结果即可

题目分析

  • 这个问题是给出了一个seed字符,生成最少添加字符形成回文后的其中一种结果

解题思路

运用剥洋葱的方式去解决

  • str的长度为nstrlps的长度为m,形成回文res的结果是2*n-m ,因为m部分已经是回文了,不需要额外添加
  • str=A1BC22DE1F,strlps=1221为例
  • 洋葱的第0层是由strlps[0]strlps[m-1],组成,即1...1,从str的最左侧开始找,一直找到strlps[0]=1的字符为止,记为leftPart,为A,接着从str的最右侧开始找,一直找到strlps[m-1]=1的字符为止,记为rightPart,为F
    • leftPart+rightPart的逆序,复制到res的左侧
    • rightPart+leftPart的逆序,复制到res的右侧
    • 结果变成了AF......FA
    • 在加上strlps,变成了AF1......1FA
  • 洋葱进入第1层,即2...2,接着第一层的位置找str,leftPartBCrightPartDE
    • leftPart+rightPart的逆序,复制到res的左侧
    • rightPart+leftPart的逆序,复制到res的右侧
    • 结果变成了BCED......DECB
    • 在加上strlps,变成了BCED2......2DECB
    • 加上上一层,变成了AF1BCED22DECB1FA
  • 洋葱进入第n层。。。
  • 代码部分注释掉了一部分,将resLeft = 0, resRight = 0;定义为全局变量,好理解些
  • 整体实现逻辑是双指针,游走,不过左右指针有很多对,嗯,只能是,细节是魔鬼啊

整体代码

Reference

  • 程序员代码面试指南

本文完

关联阅读

发表评论

电子邮件地址不会被公开。 必填项已用*标注

苏ICP备20029284号-1