动态规划+中心拓展法 5. 最长回文子串.516. 最长回文子序列 647. 回文子串_中心拓展子序列-程序员宅基地

技术标签: 算法  leetcode  动态规划  

5. 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2:

输入: “cbbd”
输出: “bb”

解题思路
子串问题,动态规划
1.最优子问题
dp[i][j],表示第i个字符到第j个字符是否是回文字符串
若dp[i+1][j-1]是回文字符串且s[i]==s[j],则dp[i][j]也为回文字符串
2.难点:边界问题
当s为单个字符时
初始条件:当s为三个字符时,前后相等即为回文字符串
大于三个字符时,用传递公式dp[i][j]=dp[i+1][j-1];

class Solution:
    def longestPalindrome(self, s: str) -> str:
        #动态规划,找到最优子问题;
        #dp[i][j],确定j,遍历i看ij是否为回文字符串;
        size=len(s)
        dp=[[False for _ in range(size)] for i in range(size)] #初始化列表
        start=0
        Lens=0        #初始化为0,不然会跳过单个字符的情况,输出至少两个字符
        if size==1:   #长度为一,特殊情况
            return s

        for j in range(1,size):         
            dp[j][j]=True         #初始化,单个为true
            for i in range(j):               
                if j-i<3 and s[i]==s[j]:      #字符串长度小于等于3时,且相等
                    dp[i][j]=True                  #为true
                elif s[i]==s[j]:                  #长度若不小于3,递推公式
                    dp[i][j]=dp[i+1][j-1]       #右上递推
                if dp[i][j] and j-i+1>Lens:    #找最大值
                    start=i                     #找起点
                    Lens=j-i                      #长度为终点-起点
        return s[start:start+Lens+1]            #输出,右闭,要+1

C++
注意点
先遍历数组,把每个数组开头的单个初始化为1,即回文串;
每个字符开头的2个字符,若相等,初始化为1,即回文串;

以i结尾的子串,遍历每一个j,若j<i-1且s[j]==s[i],则该dp[j][i]=1( j 开头, i 结尾);
若i和j隔了不只一个数且s[j]==s[i],则dp[j][i]=dp[j+1][i-1];

必须先初始化以i结尾的子串,再逐个遍历i之前的字符j
根据公式dp[i][j]=dp[i+1][j-1];
开头的字符——从后往前推;
结尾的字符——从前往后推;
所以结尾循环在外,开头循环在内,先要得到dp[每一个开头][i-1],才能得到,dp[j+1][i-1];

class Solution {
    
public:
    string longestPalindrome(string s) {
    
        //dp[i][j]  //s[i]~s[j]为回文
        int len=s.size();
        if(len<=1) return s;
        vector<bool> tmp(s.size(),0);
        vector<vector<bool>> dp(s.size(),tmp);
        
        int M=0;
        int start=0; //初始化为0,不然单个数无法输出
        int end=0;
        for(int i=0;i<len;i++)
        {
    
            for(int j=i;j>=0;j--)
            {
    
                if(s[j]==s[i])
                {
    
                    if(i<=j+2)
                        dp[j][i]=1;
                    else dp[j][i]=dp[j+1][i-1];
                }
                if(dp[j][i]&& M<i-j)
                    {
    
                        M=i-j;
                        start=j;
                        end=i;
                    }
            }
        }
        return s.substr(start,end-start+1);
    }
};

动态规划要注意递推方向

解法2:中心拓展法
每个点可以作为一个中心拓展;
每两个点的中间可作为一个中心拓展;
对每个可拓展点进行拓展,返回拓展后的回文子串长度;

拓展函数

int Expendfromcenter(string &s, int left,int right)
    {
    
        int n=s.size();
        while(left>=0&&right<n&&s[left]==s[right])
        {
    
            --left;
            ++right;
        }
        return right-left-1;//返回长度   需要-2
    }

主函数

string longestPalindrome(string s) {
    
        int len=s.size();
        int maxlen=0;
        int start=0;
        int wide=0;
        int tmp1;
        int tmp2;
        for(int i=0;i<len;i++)
        {
    
            tmp1=Expendfromcenter(s,i,i);
            tmp2=Expendfromcenter(s,i,i+1);
            if(tmp1>maxlen)
            {
       
                maxlen=tmp1;
                start=i-tmp1/2;
                wide=tmp1;
            }
            if(tmp2>maxlen)
            {
    
                maxlen=tmp2;
                start=i-(tmp2/2)+1;
                wide=tmp2;
            }
        }
        
        return s.substr(start,wide);
    }

完整代码

class Solution {
    
public:
    string longestPalindrome(string s) {
    
        int len=s.size();
        int maxlen=0;
        int start=0;
        int wide=0;
        int tmp1;
        int tmp2;
        for(int i=0;i<len;i++)
        {
    
            tmp1=Expendfromcenter(s,i,i);
            tmp2=Expendfromcenter(s,i,i+1);
            if(tmp1>maxlen)
            {
       
                maxlen=tmp1;
                start=i-tmp1/2;
                wide=tmp1;
            }
            if(tmp2>maxlen)
            {
    
                maxlen=tmp2;
                start=i-(tmp2/2)+1;
                wide=tmp2;
            }
        }
        
        return s.substr(start,wide);
    }

private:
    int Expendfromcenter(string &s, int left,int right)
    {
    
        int n=s.size();
        while(left>=0&&right<n&&s[left]==s[right])
        {
    
            --left;
            ++right;
        }
        return right-left-1;//返回长度   需要-2
    }
};

516. 最长回文子序列

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

示例 1:

输入:

"bbbab"
输出:

4

一个可能的最长回文子序列为 “bbbb”。

示例 2:

输入:

"cbbd"
输出:

2

一个可能的最长回文子序列为 “bb”。

回文子序列
回文子序列可以不连续,回文子串一定连续;

解法:动态规划
dp【i】【j】表示从i开始到j结束的子串里回文子序列的大小;

(1)初始化:dp【i】【i】为1;
(2)递推:从左往右推,从下往上推(坐下——>右上);
当s【i】==s【j】时,dp【i】【j】=dp【i+1】【j-1】+2;
当s【i】!=s【j】时,dp【i】【j】=max(dp【i+1】【j】,dp【i】【j-1】;
(3)得到结果为dp【0】【n-1】;

class Solution {
    
public:
    int longestPalindromeSubseq(string s) {
    
        //最长回文子序列——可以不连续
        int n=s.length();
        vector<int> tmp(n,0);
        vector<vector<int>> dp(n,tmp);
        for(int j=0;j<n;j++) dp[j][j]=1;

        for(int i=n-2;i>=0;i--)
            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];
    }
};

对’bbbab‘得到的dp如下:

1 2 3 3 4 
0 1 2 2 3 
0 0 1 1 3 
0 0 0 1 1 
0 0 0 0 1 

647. 回文子串

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

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

示例 1:

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

示例 2:

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

注意:

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

动态规划
对每两个ij判断是否为回文串,是则总数+1;

class Solution {
    
public:
    int countSubstrings(string s) {
    
        int n=s.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        //判断ij是不是回文
        int cnt=0;
        for(int i=n-1;i>=0;i--){
    
            dp[i][i]=1;
            ++cnt;
            for(int j=i+1;j<n;j++)
            {
    
                if(s[j]==s[i])
                {
    
                    if(j<i+2) dp[i][j]=1;
                    else dp[i][j]=dp[i+1][j-1];
                    if(dp[i][j]) ++cnt;
                }
            }
        }
        return cnt;
        }
};

若要dp i和j 之间的回文串数量,不满足最优子问题,如下,无法统计正确答案;

class Solution {
    
public:
    int countSubstrings(string s) {
    
        int n=s.size();
        vector<vector<int>> dp(n,vector<int> (n,0));
        //单个字符为一个,初始化为1
        //s[i]==s[j] dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+1;
        //s[i]!=s[j] dp[i][j]=max(dp[i+1][j],dp[i][j-1])+1;
        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]+dp[i][j-1]-dp[i+1][j-1]+1/;
            else 
                dp[i][j]=max(dp[i+1][j],dp[i][j-1])+1;
        }
        for(int i=0;i<n;i++){
    
            for(int j=0;j<n;j++)
                cout<<dp[i][j]<<" ";
                cout<<endl;
            }
        return dp[0][n-1];
    }
};

s[i]==s[j]时无法判断该子串整体是否为回文子串。

中心拓展法

对每个字符和两个字符中的点进行左右拓展,能拓展几次说明有几个回文字符串;

class Solution {
    
public:
    int countSubstrings(string s) {
    
        int n=s.size();
        int left;
        int right;
        int res=0;
        for(int i=0;i<2*n-1;i++)
        {
    
            left=i/2;
            right=left+i%2;
            while(left>=0&&right<n&&s[left]==s[right])
            {
    
                --left;++right;
                ++res;
            }
        }
        return res;
        }
};
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/BLUEsang/article/details/105051278

智能推荐

java web 获取项目路径_获取JAVA[WEB]项目相关路径的几种方法-程序员宅基地

文章浏览阅读356次。在jsp和class文件中调用的相对路径不同。 在jsp里,根目录是WebRoot 在class文件中,根目录是WebRoot/WEB-INF/classes 当然你也可以用System.getProperty("user.dir")获取你工程的绝对路径。另:在Jsp,Servlet,Java中详细获得路径的方法!1.jsp中取得路径:以工程名为TEST为例:(1)得到包含工程名的当前页面全路径:..._javaweb获取项目web路径

python实现:hangman游戏——即猜单词游戏_hangman是一个猜单词游戏,规则如下:程序从单词列表中随机选出一个单词,让用户猜测-程序员宅基地

文章浏览阅读4.5k次,点赞3次,收藏31次。思路:实现Hangman 游戏,将需要代码文件 words.txt。 它将加载到文件中的单词列表中。如果一切正常,经过一小段时间后,您应该看到以下内容:Loading word list from file...55909 words loaded.计算机必须从 words.txt 中提供的可用单词列表中随机选择一个单词。已经为您提供了加载单词列表和选择随机单词的功能。游戏必须是互..._hangman是一个猜单词游戏,规则如下:程序从单词列表中随机选出一个单词,让用户猜测

python解析xml文件之xml.etree.cElementTree和xml.etree.ElementTree区别和基本使用-程序员宅基地

文章浏览阅读161次。1、解析速度:ElementTree在 Python 标准库中有两种实现。一种是纯 Python 实现例如 xml.etree.ElementTree ,另外一种是速度快一点的 xml.etree.cElementTree 。你要记住: 尽量使用 C 语言实现的那种,因为它速度更快,而且消耗的内存更少。2、调试区别使用cElementTree的话,在pycharm的debug模..._xml.etree.celementtree write

图数据库:Neo4j的基本概念和应用场景_neo4j 典型 场景-程序员宅基地

文章浏览阅读4.5k次。Neo4j的基本概念和应用场景1. 基本概念每个标签下可以有N个节点,每个节点代表一个对象,相当于数据表里面的一行数据节点质检的连线代表对象质检的关系,节点和关系都可以带若干属性1.1 标签-Label:相当于数据表1.2 节点-Node:相当于数据表李的一行数据1.3 关系-Relation2. 图数据库基础 Cypher2.1 什么是Cypher2.1.1 背景介绍属性图模型以及其上的Cypher查询语言最早定义于著名的图数据库系统——Neo4j。Neo4j是由Neo4j公司开_neo4j 典型 场景

基于python中jieba包的中文分词中详细使用_jieba.analyse.set_stop_words-程序员宅基地

文章浏览阅读2.1k次,点赞2次,收藏10次。为了教别人jieba库的使用,顺便自己把这个整理一下,记录下来,省的之后使用又来找资料jieba:中文分词比较好,但是英文分词就用其他的3种分词模式:精确模式,将句子精确地切开,不存在冗余,适合文本分析;全模式,把句子中所有的可以成词的词语都扫描出来,速度非常快,但是不能解决歧义,有冗余;搜索引擎模式,在精确模式的基础上,对长词再次切分,提高召回率,适合用于引擎分词jieba...._jieba.analyse.set_stop_words

重写用户模型时报错AttributeError: type object ‘自定义类’ has no attribute ‘USERNAME_FIELD’...-程序员宅基地

文章浏览阅读1.6k次。view中导入:from django.contrib.auth.models import AbstractBaseUsersettings.py中设置了:AUTH_USER_MODEL='app名.model自定义类'解决方法:在自定义类中加:  identifier = models.CharField(max_length=40, unique=True)  USERNAME_..._model=dashscope.generation.models.qwen_72b_chat, attributeerror: type object

随便推点

java对象的内存布局_java object 类 内存布局-程序员宅基地

文章浏览阅读6.2k次。我们用如下代码来说一下java对象的内存布局。class A { long l; int i;}class B extends A { long l; int i;} 如图所示展示的是new B()在堆中的内存模型: JVM中,每个对象都有一个对象头(图中黄色部分),由标记字段和类型指针构成,标记字段存储has..._java object 类 内存布局

tf.reduce.mean()用法_tf.math.reduce_mean()-程序员宅基地

文章浏览阅读2.8k次。感谢:https://tensorflow.google.cn/api_docs/python/tf/math/reduce_mean别名: tf.math.reduce_mean tf.reduce_mean 两种叫法都可以~ tf.math.reduce_mean( input_tensor, axis=None, keepdims=None,..._tf.math.reduce_mean()

程序员常用的开源网站-程序员宅基地

文章浏览阅读868次。1、博客园 http://www.cnblogs.com/ 创立于2004年,是一个面向程序员的在线学习社区。“活到老,学到老”是程序人生最真实的写照,学习不仅需要一个人的刻苦努力,更需要一个学习气氛浓、乐于分享、互相帮助的社区。 2、 知乎 http://www.zhihu.com/ 国内最大的社交问答社区,非常多的程序员技术、职场讨论话题和大牛在分享内容。 3、github ..._程序员开源网站

GET请求参数有URL或特殊符号怎么办?_get请求url有特殊符号-程序员宅基地

文章浏览阅读1.9w次。在发起GET请求的时候有一种情况,那就是参数包含URL参数,如下:http://www.abc123.com?url=http://www.def456.com?id=5&amp;userName=adminGET请求地址中参数url的值为 http://www.def456.com?id=5&amp;userName=admin 这样会造成什么问题?你的服务器接收到的url参..._get请求url有特殊符号

CSDN 博客被自己误删了怎么办---(联系QQ客服)_csdn被删了会有记录吗-程序员宅基地

文章浏览阅读404次。不小心删除的博客都还在回收站中,只要不点击彻底删除就会一直存在。恢复: 页面下拉找到客服说明意图然后提供 用户名 就好啦_csdn被删了会有记录吗

IDEA 的安装、配置与使用(超详细)_idea配置-程序员宅基地

文章浏览阅读5.6w次,点赞83次,收藏383次。一、IntelliJ IDEA 介绍1.JetBrains 公司介绍IDEA(https://www.jetbrains.com/idea/)是 JetBrains 公司的产品,公司旗下还有其它产品,比如:WebStorm:用于开发 JavaScript、HTML5、CSS3 等前端技术;PyCharm:用于开发 pythonPhpStorm:用于开发 PHPRubyMine:用于开..._idea配置

推荐文章

热门文章

相关标签