c++--动态规划回文串问题

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

1.回文子串   力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

给定一个字符串 s ,请计算这个字符串中有多少个回文子字符串。

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

示例 1:

输入:s = "abc"
输出:3
解释:三个回文子串: "a", "b", "c"

示例 2:

输入:s = "aaa"
输出:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa

分析:

c++--动态规划回文串问题,c++,动态规划,开发语言

 文章来源地址https://www.toymoban.com/news/detail-666263.html

class Solution {
public:
    int countSubstrings(string s) 
    {
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        int ret=0;
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    if(i==j)
                        dp[i][j]=true;
                    else
                    {
                        if(i+1<j)
                            dp[i][j]=dp[i+1][j-1]==true?true:false;
                        else
                        dp[i][j]=true;
                    }
                }
                if(dp[i][j]==true)
                    ret+=1;
            }
        }
        return ret;
    }
};

2.最长回文串  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

给你一个字符串 s,找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

分析:这道题和上一道题差不多,上一道题会做后,知道题自己思考下

class Solution {
public:
    string longestPalindrome(string s) 
    {
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        
        int begin=0,len=0;
        //string s1;
        for(i=n-1;i>=0;i--)
        {
            for(j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    if(i==j)
                        dp[i][j]=true;
                    else
                    {
                        dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                    }
                    if(dp[i][j] && j - i + 1 > len) 
                        len = j - i + 1, begin = i;
                }
            }
        }
      
        return s.substr(begin,len);

    }
};

3.回文串分割  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

给你一个字符串 s ,如果可以将它分割成三个 非空 回文子字符串,那么返回 true ,否则返回 false 。

当一个字符串正着读和反着读是一模一样的,就称其为 回文字符串

示例 1:

输入:s = "abcbdd"
输出:true
解释:"abcbdd" = "a" + "bcb" + "dd",三个子字符串都是回文的。

示例 2:

输入:s = "bcbddxy"
输出:false
解释:s 没办法被分割成 3 个回文子字符串。

分析:先把所有的回文子串找出来,然后寻找是否可以组成三段的

class Solution {
public:
    bool checkPartitioning(string s) 
    {
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    if(i==j)
                        dp[i][j]=true;
                    else
                        dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                }
            }
        }
        for(int i=1;i<n;i++)
        {
            for(int j=i;j<n-1;j++)
            {
                if(dp[0][i-1]&&dp[i][j]&&dp[j+1][n-1])
                {
                    return true;
                }
            }
        }
        return false;
    }
};

4.分割回文串2 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。

返回符合要求的 最少分割次数

示例 1:

输入:s = "aab"
输出:1
解释:只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2:

输入:s = "a"
输出:0

示例 3:

输入:s = "ab"
输出:1
class Solution {
public:
    int minCut(string s) 
    {
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    if(i==j)
                        dp[i][j]=true;
                    else
                        dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                }
            }
        }
        vector<int> arr(n,0x3f3f3f3f);
        for(int i=0;i<n;i++)
        {
           if(dp[0][i]==true) arr[i]=0;
           else
           {
                for(int j=1;j<=i;j++)
                {
                    if(dp[j][i])
                    arr[i]=min(arr[i],arr[j-1]+1);
                }
           }
        }
        return arr[n-1];
    }
};

5.最长回文子序列  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

示例 1:

输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。

示例 2:

输入:s = "cbbd"
输出:2
解释:一个可能的最长回文子序列为 "bb" 。

分析:关于「回⽂⼦序列」和「回⽂⼦串」的分析⽅式,⼀般都是⽐较固定的,都是选择这段区域的「左右端点」的字符情况来分析。因为如果⼀个序列是回⽂串的话,「去掉⾸尾两个元素之后依旧是回⽂串」,「⾸尾加上两个相同的元素之后也依旧是回⽂串」。因为,根据「⾸尾元素」的不同,可以分为下⾯两种情况:
i. 当⾸尾两个元素「相同」的时候,也就是 s[i] == s[j] :那么 [i, j] 区间上的最⻓回⽂⼦序列,应该是 [i + 1, j - 1] 区间内的那个最⻓回⽂⼦序列⾸尾填上s[i] 和 s[j] ,此时 dp[i][j] = dp[i + 1][j - 1] + 2
ii. 当⾸尾两个元素不「相同」的时候,也就是 s[i] != s[j] :此时这两个元素就不能同时添加在⼀个回⽂串的左右,那么我们就应该让 s[i] 单独加在⼀个序列的左边,或者让 s[j] 单独放在⼀个序列的右边,看看这两种情况下的最⼤值:
• 单独加⼊ s[i] 后的区间在 [i, j - 1] ,此时最⻓的回⽂序列的⻓度就是 dp[i][j - 1] ;
• 单独加⼊ s[j] 后的区间在 [i + 1, j] ,此时最⻓的回⽂序列的⻓度就是 dp[i+ 1][j] ;取两者的最⼤值,于是 dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]) 。
综上所述,状态转移⽅程为:
▪ 当 s[i] == s[j] 时: dp[i][j] = dp[i + 1][j - 1] + 2
▪ 当 s[i] != s[j] 时: dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
 

class Solution {
public:
    int longestPalindromeSubseq(string s) 
    {
        int n=s.size();
        vector<vector<int>> dp(n,vector<int>(n));
        
        for(int i=n-1;i>=0;i--)
        {
            dp[i][i]=1;
            for(int j=i+1;j<n;j++)
            if(s[i]==s[j])
            {
                dp[i][j]=dp[i+1][j-1]+2;
            }
            else
            {
                dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
            }
        }
        return dp[0][n-1];
    }
};

6.让字符串成为回文串最小插入次数   力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

给你一个字符串 s ,每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

示例 1:

输入:s = "zzazz"
输出:0
解释:字符串 "zzazz" 已经是回文串了,所以不需要做任何插入操作。

示例 2:

输入:s = "mbadm"
输出:2
解释:字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

示例 3:

输入:s = "leetcode"
输出:5
解释:插入 5 个字符后字符串变为 "leetcodocteel" 。

分析:

c++--动态规划回文串问题,c++,动态规划,开发语言

 

class Solution {
public:
    int minInsertions(string s) 
    {
        int n=s.size();
        vector<vector<int>> dp(n,vector<int>(n));
        for(int i=n;i>=0;i--)
        {
            for(int j=i+1;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    dp[i][j]=dp[i+1][j-1];
                }
                else if(s[i]!=s[j])
                {
                    dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1; 
                }
            }
        }
        return dp[0][n-1];
    }
};

到了这里,关于c++--动态规划回文串问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 动态规划课堂6-----回文串问题

    目录 引言: 例题1:回文子串 例题2:回文串分割IV 例题3:分割回文串II 例题4:最长回文子序列 例题5:让字符串成为回文串的最小插入次数 回文字符串  是正着读和倒过来读一样的字符串。 动态规划的回文串问题一般是把 子串 是否是回文串的信息保持在dp表里面,所以更

    2024年03月18日
    浏览(48)
  • c++--动态规划回文串问题

    1.回文子串   力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 给定一个字符串 s ,请计算这个字符串中有多少个回文子字符串。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。 示例 1: 示例 2: 分析:   2.最长回文串  力扣(

    2024年02月11日
    浏览(38)
  • day57|动态规划17-最长回文子串问题

    回文子串:强调连续 回文子序列:不强调连续 暴力思路:三层for循环 双指针思路: 动态规划 dp数组 dp[i][j]: 根据字符串的形式和所解决的问题确定dp数组的形式和含义。 递归公式 (分情况讨论) 2.1 如果 i j 2.2 如果 j-i 1 2.3 如果 j-i1: 此时依赖于dp[i+1][j-1]是不是一个回文子

    2024年02月09日
    浏览(43)
  • 最长回文子序列问题的原理与实现:动态规划的又一经典应用

    回文是指一个正着读和反着读都一样的字符串,比如 “aba” , “racecar” , “madam” 等。回文有许多有趣的性质和应用,比如在密码学,生物信息学,数据压缩等领域都有涉及。 那么,给定一个字符串,如何找出它的最长回文子序列呢?最长回文子序列是指从原字符串中删

    2023年04月13日
    浏览(49)
  • 动态规划-最长的回文序列

    该题是lintcode上 667 · 最长的回文序列,该题的解题思路亦是参考了九章侯老师的解题思路给出。 给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 1000. 输入: “bbbab” 输出: 4 解释: 一个可能的最长回文序列为 “bbbb” 输入: “bbbbb” 输出:

    2024年02月09日
    浏览(48)
  • 动态规划-最长回文子串

    突然觉得很有必要将学过的内容记录下来,这样后续在需要用到的时候就可以避免从头进行学习,而去看自己之前做过的笔记无疑是效率更高的方法。 而作为计算机专业的学生,纸质笔记无法很好的进行记录,像写代码、画图、画表都是很麻烦的,而且纸质的很容易丢,因此

    2024年04月14日
    浏览(38)
  • 动态规划——最长回文子串

    给你一个字符串 s ,找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 示例 1: 示例 2: 1、动态规划算法 解题思路 (1)考虑 回文串的性质 :若一个子串是回文串并且 长度大于2 ,则将其 首尾两个字母去除 后,该子串仍然是一

    2024年04月08日
    浏览(51)
  • 动态规划 回文子串

    647. 回文子串 双指针法: 遍历回文中心----一个回文中心----两个回文中心 遍历边界,找出回文中心, 其实还是变相的找回文中心 动态规划: 4. dp[i][j]:表示区间范围[i,j] (注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false 5. 当s[i]与s[j]不相等,那没

    2024年02月15日
    浏览(45)
  • 动态规划-分割回文串 II

    跟着九章侯老师学习了动态规划专题之后根据学习所总结: 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 输入:s = “aab” 输出:1 解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。 输入:s = “

    2024年02月10日
    浏览(49)
  • 力扣第131题 分割回文串 c++ 回溯+简单 动态规划(是否为回文子串)

    131. 分割回文串 中等 相关标签 字符串   动态规划   回溯 给你一个字符串  s ,请你将   s   分割成一些子串,使每个子串都是  回文串  。返回  s  所有可能的分割方案。 回文串  是正着读和反着读都一样的字符串。 示例 1: 示例 2: 提示: 1 = s.length = 16 s  仅由小写

    2024年02月07日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包