647.回文子串 516.最长回文子序列

这篇具有很好参考价值的文章主要介绍了647.回文子串 516.最长回文子序列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

647.回文子串 516.最长回文子序列

647.回文子串

力扣题目链接(opens new window)

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

示例 1:

  • 输入:“abc”
  • 输出:3
  • 解释:三个回文子串: “a”, “b”, “c”

示例 2:

  • 输入:“aaa”
  • 输出:6
  • 解释:6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示:输入的字符串长度不会超过 1000 。

思路

思路:动态规划
动态规划五部曲
1.定义dp数组以及下标含义
做了很多动态规划的题目。定义Dp数组很容易想到,题目要求什么,我们就定义什么
但对于【回文子串】题目来说。若定义dp[i]为以字符s.chat(i)为结尾字符串中,有多少个回文子串。
dp[i-1]和dp[i],dp[i+1] 其实没关联。需要换一种定义方式
需要看回文字符串性质来定义dp数组。如下图所示:

647.回文子串 516.最长回文子序列,算法,数据结构,leetcode,java

在确定s[1],s[2],s[3]为回文字符串,只需要判断s[0]是否等于s[4]。如果相同,那么s就是回文字符串
可以得到一种递推关系。即判断字符串是否回文(字符串范围【i,j]),要看【i+1,j-1]是否回文
所以定义二维Dp数组。dp[i][j].true表示闭区间【i,j]是回文字符串,false表示【i,j]不是回文字符串
2.定义递推公式
当s[i]与s[j]不相等,那没啥好说的了,dp[i][j]一定是false。
当s[i]与s[j]相等时,这就复杂一些了,有如下三种情况

情况一:下标i 与 j相同,同一个字符例如a,当然是回文子串
情况二:下标i 与 j相差为1,例如aa,也是回文子串
情况三:下标:i 与 j相差大于1的时候,例如cabac,此时s[i]与s[j]已经相同了,我们看i到j区间是不是回文子串就看aba是不是回文就可以了,那么aba的区间就是 i+1 与 j-1区间,这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
3.dp数组初始化
dp数组初始化为false即可。
4.确定遍历顺序
有递推公式可得dp[i][j] 可由dp[i+1][j-1]得到
可以得出。先有 i+1,再有i.先有j-1,再有j
所以i需要从大到小遍历,j需要从小到大遍历。但因为【i,j]是闭区间,j一定是大于等于i的
所以对j遍历时,要以i为起始位置
5.举例推导dp数组
时间复杂度:O(n^2)
空间复杂度:O(n^2)

代码如下

public int countSubstrings(String s) {
    if (s == null)// 边缘条件判断
        return 0;
    if (s.equals("") || s.length() == 1)
        return 1;

    boolean[][] dp = new boolean[s.length()][s.length()];// 定义dp数组并初始化,默认值为false
    int result = 0;// 回文字符串数量
    for (int i = s.length() - 1; i >= 0; i--) {
        for (int j = i; j < s.length(); j++) {
            if (s.charAt(i) == s.charAt(j)) {
                if (i == j) {// i,j表示同一个字符
                    result++;
                    dp[i][j] = true;
                } else if (i + 1 == j) {//i,j紧挨
                    dp[i][j] = true;
                    result++;
                } else {//i,j不紧挨
                    dp[i][j] = dp[i + 1][j - 1];
                    if (dp[i][j])
                        result++;
                }
            }

        }
    }

    return result;
}

516.最长回文子序列

力扣题目链接(opens new window)

给定一个字符串 s ,找到其中最长的回文子序列,并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1: 输入: “bbbab” 输出: 4 一个可能的最长回文子序列为 “bbbb”。

示例 2: 输入:“cbbd” 输出: 2 一个可能的最长回文子序列为 “bb”。

提示:

  • 1 <= s.length <= 1000
  • s 只包含小写英文字母

思路

思路:动态规划
1.定义dp数组以及下标含义
定义二维Dp数组。dp[i][j].表示闭区间[i,j]范围内,最长回文子序列长度
2.定义递推公式加入
当s[i]与s[j]不相等
分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
加入s[j]的回文子序列长度为dp[i + 1][j]。
加入s[i]的回文子序列长度为dp[i][j - 1]。
那么dp[i][j]一定是取最大的,即:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
举例如下。   s = bbbba
当i = 0 s[0] = b ,j = 4 s[4] = a
 dp[i+1][j-1] = dp[1][3] = bbb = 3;
此时分别加入s[0]和s[4],看看哪一个可以组成最长的回文子序列。
很显然加入s[0]可以组成最长的回文子序列,长度为4

当s[i]与s[j]相等时
【i,j】闭区间内最长回文子串的长度 == dp[i+1][j-1] + 2
即dp[i][j] = dp[i+1][j-1] + 2
3.dp数组初始化
首先要考虑当i 和j 相同的情况,从递推公式:dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。
所以需要手动初始化一下,当i与j相同,那么dp[i][j]一定是等于1的,即:一个字符的回文子序列长度就是1。
其他情况dp[i][j]初始为0就行,这样递推公式:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖
4.确定遍历顺序
有递推公式可得dp[i][j] 可由dp[i+1][j-1]得到
可以得出。先有 i+1,再有i.先有j-1,再有j
所以i需要从大到小遍历,j需要从小到大遍历。但因为【i,j]是闭区间,j一定是大于等于i的
所以对j遍历时,要以i为起始位置
5.举例推导dp数组
时间复杂度:O(n^2)
空间复杂度:O(n^2)

代码如下

public static void main(String args[]) {
    longestPalindromeSubseq("bbbab");
}

public static int longestPalindromeSubseq(String s) {
    if (s.equals("")) {
        return 0;
    }
    int[][] dp = new int[s.length()][s.length()];// dp数组默认值false
    for (int i = s.length() - 1; i >= 0; i--) {
        for (int j = i; j < s.length(); j++) {
            if (s.charAt(i) == s.charAt(j)) {
                if (i == j)
                    dp[i][j] = 1;// 对dp数组的初始化。遍历过程中初始化即可
                else if (i == (j - 1))
                    dp[i][j] = 2;
                else
                    dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][s.length() - 1];
}

问题

问题
使用52.回文子串的思路,只能求出最长连续的回文子序列
无法求出不连续的回文子序列
错误代码文章来源地址https://www.toymoban.com/news/detail-806184.html

public int longestPalindromeSubseq(String s) {
    if (s.equals("")) {
        return 0;
    }
    boolean[][] dp = new boolean[s.length()][s.length()];// dp数组默认值false
    int strMaxLength = 0;

    for (int i = s.length() - 1; i >= 0; i--) {
        for (int j = i; j < s.length(); j++) {
            if (s.charAt(i) == s.charAt(j)) {
                if (i == j) {
                    dp[i][j] = true;
                    if (dp[i][j]  && (j - i + 1) > strMaxLength)
                        strMaxLength = 1;
                } else if (i == j - 1) {
                    dp[i][j] = true;
                    if (dp[i][j]  && (j - i + 1) > strMaxLength)
                        strMaxLength = 2;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                    if (dp[i][j]  && (j - i + 1) > strMaxLength)
                        strMaxLength = (j - i + 1);
                }

            }
        }
    }
    return strMaxLength;
}

到了这里,关于647.回文子串 516.最长回文子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录 Day - 59|#647 回文字串|#516 最长回文子序列

    ● 647. 回文字串 ● 516. 最长回文子序列 给你一个字符串 s ,请你统计并返回这个字符串中回文子串的数目。 回文字符串是正着读和倒过来读一样的字符串。 子字符串是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成

    2024年02月07日
    浏览(43)
  • leetcode 516. 最长回文子序列(JAVA)题解

    题目链接 https://leetcode.cn/problems/longest-palindromic-subsequence/description/?utm_source=LCUSutm_medium=ip_redirectutm_campaign=transfer2china 目录 题目描述: 暴力递归: 动态规划: 给你一个字符串  s  ,找出其中最长的回文子序列,并返回该序列的长度。子序列定义为:不改变剩余字符顺序的情况

    2024年02月13日
    浏览(44)
  • 每天一道leetcode:516. 最长回文子序列(动态规划&中等)

    给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 1 = s.length = 1000 s 仅由小写英文字母组成 动态规划 ,使用二维dp数组记录[i,j]间的最大回文子序列长度

    2024年02月13日
    浏览(48)
  • ( 动态规划) 516. 最长回文子序列 ——【Leetcode每日一题】

    难度:中等 给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入:s = “bbbab” 输出:4 解释:一个可能的最长回文子序列为 “bbbb” 。 示例

    2024年02月06日
    浏览(44)
  • 【算法沉淀】最长回文子串

     🎉🎉欢迎光临🎉🎉 🏅我是苏泽,一位对技术充满热情的探索者和分享者。🚀🚀 🌟特别推荐给大家我的最新专栏 《数据结构与算法:初学者入门指南》📘📘 希望能和大家一起学习!共同进步! 这是苏泽的个人主页可以看到我其他的内容哦👇👇 努力的苏泽 http://su

    2024年03月12日
    浏览(46)
  • leetcode 647. 回文子串

    题目链接:leetcode 647 给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不

    2024年02月05日
    浏览(37)
  • 最长子串和回文子串相关的算法题解

    中等 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。 示

    2024年02月19日
    浏览(41)
  • 【算法Hot100系列】最长回文子串

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月04日
    浏览(37)
  • 【算法|动态规划No30】leetcode5. 最长回文子串

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(41)
  • ( 字符串) 647. 回文子串 ——【Leetcode每日一题】

    难度:中等 给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串

    2024年02月01日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包