动态规划:最长回文子串 & 最长回文子序列

动态规划:最长回文子串 & 最长回文子序列一、题目所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如“a”、“aba”、“abba”。对于一个字符串,其子串是指连续的一段子字符串,而子序列是可以非连续的一段子字符串。最长回文子串和最长回文子序列(LongestPalindromicSubsequence)是指任意一个字符串,它说包含的长度最长的回文子串和回文子序列。例如:字符串“ABCDDCEFA…

大家好,又见面了,我是你们的朋友全栈君。

一、题目

所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如 “a”、“aba”、“abba”。

对于一个字符串,其子串是指连续的一段子字符串,而子序列是可以非连续的一段子字符串。

最长回文子串最长回文子序列(Longest Palindromic Subsequence)是指任意一个字符串,它说包含的长度最长的回文子串和回文子序列。

例如:字符串 “ABCDDCEFA”,它的 最长回文子串 即 “CDDC”,最长回文子序列 即 “ACDDCA”。

二、最长回文子串

1. 思路

首先这类问题通过穷举的办法,判断是否是回文子串并再筛选出最长的,效率是很差的。我们使用 动态规划 的策略来求解它。首先我们从子问题入手,并将子问题的解保存起来,然后在求解后面的问题时,反复的利用子问题的解,可以极大的提示效率。

由于最长回文子串是要求连续的,所以我们可以假设 j 为子串的起始坐标,i 为子串的终点坐标,其中 ij 都是大于等于 0 并且小于字符串长度 length 的,且 j <= i,这样子串的长度就可以使用 i - j + 1 表示了。

我们从长度为 1 的子串依次遍历,长度为 1 的子串肯定是回文的,其长度就是 1;然后是长度为 2 的子串依次遍历,只要 str[i] 等于 str[j] ,它就是回文的,其长度为 2;接下来就好办了,长度大于 2 的子串,如果它要满足是回文子串的性质,就必须有 str[i] 等于 str[j] ,并且去掉两头的子串 str[j+1 ... i-1] 也一定是回文子串,所以我们使用一个数组来保存以 j 为子串起始坐标,i 为子串终点坐标的子串是否是回文的,由于我们是从子问题依次增大求解的,所以求解 [i ... j] 的问题时,比它规模更小的问题结果都是可以直接使用的了。

2. 代码

public class Main { 
   
  
    public static void main(String[] args) { 
   
        String s = "cabbaeeaf";
        System.out.println(getLPS(s));
    }
      
    public static String getLPS(String s) { 
   
        char[] chars = s.toCharArray();
        int length = chars.length;
        // 第一维参数表示起始位置坐标,第二维参数表示终点坐标
        // lps[j][i] 表示以 j 为起始坐标,i 为终点坐标是否为回文子串
        boolean[][] lps = new boolean[length][length];
        int maxLen = 1; // 记录最长回文子串最长长度
        int start = 0; // 记录最长回文子串起始位置
        for (int i = 0; i < length; i++) { 
   
            for (int j = 0; j <= i; j++) { 
   
                if (i - j < 2) { 
   
                    // 子字符串长度小于 2 的时候单独处理
                    lps[j][i] = chars[i] == chars[j];
                } else { 
   
                    // 如果 [i, j] 是回文子串,那么一定有 [j+1, i-1] 也是回子串
                    lps[j][i] = lps[j + 1][i - 1] && (chars[i] == chars[j]);
                }
                if (lps[j][i] && (i - j + 1) > maxLen) { 
   
                    // 如果 [i, j] 是回文子串,并且长度大于 max,则刷新最长回文子串
                    maxLen = i - j + 1;
                    start = j;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
      
}

三、最长回文子序列

1. 思路

子序列的问题将比子串更复杂,因为它是可以不连续的,这样如果穷举的话,问题规模将会变得非常大,我们依旧是选择使用 动态规划 来解决。

首先我们假设 str[0 ... n-1] 是给定的长度为 n 的字符串,我们使用 lps(0, n-1) 表示以 0 为起始坐标,长度为 n-1 的最长回文子序列的长度。那么我们需要从子问题开始入手,即我们一次遍历长度 1 到 n-1 的子串,并将子串包含的 最长回文子序列的长度 保存在 lps 的二维数组中。

遍历过程中,回文子序列的长度一定有如下性质:

  • 如果子串的第一个元素 str[j] 和最后一个元素 str[i+j] 相等,那么 lps[j, i+j] = lps[j+1, i+j-1] + 2,其中 lps[j+1, i+j-1] 表示去掉两头元素的最长子序列长度。
  • 如果两端的元素不相等,那么lps[j, i+j] = max(lps[j][i+j-1], lps[j+1][i+j]),这两个表示的分别是去掉末端元素的子串和去掉起始元素的子串。

2. 代码

public class Main { 

public static void main(String[] args) { 

String s = "cabbeaf";
System.out.println(getLPS(s));
}
public static int getLPS(String s) { 

char[] chars = s.toCharArray();
int length = chars.length;
// 第一维参数表示起始位置的坐标,第二维参数表示长度,使用 0 表示长度 1
int[][] lps = new int[length][length];
for (int i = 0; i < length; i++) { 

lps[i][i] = 1; // 单个字符的最长回文子序列长度为1,特殊对待一下
}
// (i + 1) 表示当前循环的子字符串长度
for (int i = 1; i < length; i++) { 

// j 表示当前循环的字符串起始坐标
for (int j = 0; i + j < length; j++) { 

// 即当前循环的子字符串坐标为 [j, i + j]
// 所以第一个字符是 chars[j],最后一个字符就是 chars[i + j]
if (chars[j] == chars[i + j]) { 

lps[j][i + j] = lps[j + 1][i + j - 1] + 2;
} else { 

lps[j][i + j] = Math.max(lps[j][i + j - 1], lps[j + 1][i + j]);
}
}
}
// 最大值一定在以0为起始点,长度为 length - 1 的位置
return lps[0][length - 1];
}
}

最后,这题只返回了最长回文子序列的长度,一般面试题中也只是要求返回长度即可。但是如果你也想知道最长回文子序列具体是啥,这可以额外添加一个变量记录最长回文子序列是哪些字符,例如维护一个键为 lps[j][i + j],值为 String 的 map。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/131000.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • VC编程入门浅谈「建议收藏」

    VC编程入门浅谈「建议收藏」
    学VC并不是传说的那么难,可不下些功夫是学不成的。学编程急不得,没有编程的基础知识上来就学VC肯定碰一头灰,说VC难就难在这点上了。如果硬上,意志坚强的话还能挺过来,但最后还得回头来补习基础知识。意志不坚强的话,很有可能就此放弃,并留下一个VC难得不得了的印象。

      其实,只要踏踏实实一步一步来,学VC很简单。对于没有编程基础的人首先要学习编程的基础知识,如变量,语句,基本的算法等,然后写一些小的程序,实现些常用算法对自己的思维是很好的锻炼,对以后的学习大有好处。起码要能排

  • MySQL 添加索引,删除索引及其用法[通俗易懂]

    MySQL 添加索引,删除索引及其用法[通俗易懂]原文:https://www.cnblogs.com/zz-tt/p/6609828.html一.索引的作用一般的应用系统,读写比例在10:1左右,而且插入操作和一般的更新操作很少出现性能问题,遇到最多的,也是最容易出问题的,还是一些复杂的查询操作,所以查询语句的优化显然是重中之重。在数据量和访问量不大的情况下,mysql访问是非常快的,是否加索引对访问影响…

  • Latex插入图片参数设置

    Latex插入图片参数设置常用选项[htbp]是浮动格式:『h』当前位置。将图形放置在正文文本中给出该图形环境的地方。如果本页所剩的页面不够,这一参数将不起作用。『t』顶部。将图形放置在页面的顶部。『b』底部。将图形放置在页面的底部。『p』浮动页。将图形放置在一只允许有浮动对象的页面上。一般使用[htb]这样的组合,只用[h]是没有用的。这样组合的意思就是latex会尽量满足排在前面的浮动格式,就是h-t-b这个…

  • ELK 收集 Tomcat 日志「建议收藏」

    ELK 收集 Tomcat 日志「建议收藏」01Tomcat安装与测试1.1安装Tomcat安装Tomcat的本体和相关官方测试demo,参考链接apt-getinstalltomcat8-y#安装Tomcat本体apt-getinstalltomcat8-docstomcat8-examplestomcat8-admin-y#安装测试demo1.2Tomcat启动检查systemctlstarttomcat8#启动Tomcatsystemctlstatustomcat8netstat

  • java后端开发职责_工作职责和岗位职责有什么区别

    java后端开发职责_工作职责和岗位职责有什么区别java后台开发岗位职责:1.参与项目后端的设计、开发工作,承担核心功能模块的代码编写,确保项目进度和质量;2.参与开发人员codereview工作,并能提供性能优化、安全性建议;3.参与系统架构设计、接口规范制定、技术文档编写等。4.参与现有系统的优化改进。岗位要求:1.本科及以上学历,计算机相关专业优先,【扎实的数据结构/算法与编码能力】;2.JAVA基础扎实,1年及以上JAV…

  • goland 激活码2020【在线破解激活】

    goland 激活码2020【在线破解激活】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号