精华内容
下载资源
问答
  • 主要为大家详细介绍了js如何找出字符串中的最长回文串的方法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • python最长回文串算法

    2020-12-23 13:52:17
    给定一个字符,要求在这个字符中找到符合回文性质的最长子串。所谓回文性是指诸如 “aba”,”ababa”,”abba”这类的字符,当然单个字符以及两个相邻相同字符也满足回文性质。 看到这个问题,最先想到的解决...
  • 1、确定动态规划方程:dp[j][k] - 表示以下标为 j 为开始,以下标为 k 为结束的字符串是否为回文串; 2、确定状态转移方程: 当字符串长度为0时,返回空字符串“”; 当字符串长度为1时,都是回文串; 当字符串长度...

    题目

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

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

    注意点

    1、确定动态规划方程:dp[j][k] - 表示以下标为 j 为开始,以下标为 k 为结束的字符串是否为回文串;
    2、确定状态转移方程:

    • 当字符串长度为0时,返回空字符串“”;
    • 当字符串长度为1时,都是回文串;
    • 当字符串长度为2时,当两个字符相同时为回文串;
    • 当字符串长度大于2时,当头尾两字符相等,且dp[j + 1][k - 1]为回文串时,当前字符串为回文串。(当字符串长度大于2时,一个字符串要为回文串,则首尾一定相同,且除去首位的字符串一定为回文串;比如abba,头尾都为a,且bb为回文串,所以abba也为回文串)

    实现

    class Solution {
        public String longestPalindrome(String s) {
            int length = s.length();
            // 定义动态规划方程
            boolean[][] dp = new boolean[length][length];
            // 最长回文自创默认为空字符串
            String reslut = "";
    
    		/* 动态规划过程
    			i:表示判断字符串的长度;
    			j:表示判断字符串开始下标;
    			k:表示判断字符串结束下标
    		*/
    		// 按字符串长度从1(0代表长度为1)开始遍历
            for (int i = 0; i < length; i ++) {
            	// 根据字符串长度从头开始遍历(确定开始下标)
                for (int j = 0; j + i < length; j ++) {
                	// 确定结束下标
                    int k = j + i;
                    
                    // 字符串长度为1的情况
                    if (i == 0) {
                    	// 都是回文串
                        dp[j][k] = true;
                        
                    // 字符串长度为2的情况
                    } else if (i == 1) {
                        // 当两字符相等时为回文串
                        dp[j][k] = (s.charAt(j) == s.charAt(k));
                        
                    // 字符串长度大于2的情况    
                    } else {
                    	// 头尾两字符相等,且dp[j + 1][k - 1]为回文串时,当前字符串为回文串
                        dp[j][k] = (s.charAt(j) == s.charAt(k)) && dp[j + 1][k - 1];
                    }
    
    				// 更新最长回文子串
                    if (dp[j][k] && i + 1 > reslut.length()) {
                        reslut = s.substring(j, k + 1);
                    }
                }
            }
    		
    		// 返回结果
            return reslut;
        }
    }
    
    展开全文
  • 这是自己第一次做出来动态规划的问题,感觉还是挺有成就感的。 我们用i来指向字符串的开头,用j来指向字符串的结尾。判断字符串为回文串的其中一个条件为s[i]==s[j]。 另一个条件为s[i+1]==s[j-

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

    示例 1:

    输入:s = “babad”
    输出:“bab”
    解释:“aba” 同样是符合题意的答案。
    示例 2:

    输入:s = “cbbd”
    输出:“bb”
    示例 3:

    输入:s = “a”
    输出:“a”
    示例 4:

    输入:s = “ac”
    输出:“a”

    这是自己第一次做出来动态规划的问题,感觉还是挺有成就感的。
    我们用i来指向字符串的开头,用j来指向字符串的结尾。判断字符串为回文串的其中一个条件为s[i]==s[j]。
    另一个条件为s[i+1]==s[j-1]。即两边相等之后,中间的内容也要相等。
    根据以上两个条件,我们就可以写出状态转移方程
    dp[i][j]=dp[i+1][j-1]^s[i]==s[j]

    对于长度为1的字符串,他显然是一个回文串。而长度为2的字符串,当两个字母相等时为回文串。于是我们可以写出动态规划的边界条件
    dp(i,i)=true;
    dp(i,i+1)=(s[i]==s[j])
    这样我们就可以完成动态规划了,最终的答案就是所有dp[i][j]=true中j-i+1(即字符串长度)的最大值
    注意:在状态转移方程中,我们是从长度较短的字符串向长度较长的字符串进行转移的,因此一定要注意动态规划的循环顺序。

    /**
     * @param {string} s
     * @return {string}
     */
    var longestPalindrome = function(s) {
        //dp[i][j]=dp[i+1][j-1]&&s1[i]===s1[j]
        //初始化二维数组
        const s1=s.split('')
        const len = s.length
        let maxLen=1
        let start=0
        let dp = new Array(len)
        for(let i =0; i<len;i++) {
            dp[i]=new Array(len);
            for(let j=0;j<len;j++) {
                dp[i][j]=0;
            }
            dp[i][i]=1
        }
        //先枚举答案字串长度,从长度最小的子问题开始
        for(let L=2;L<=len;L++) {
            //枚举左边界
            for(let i=0;i<len;i++) {
                let j = L+i-1
                if(j>=len) break//右边界越界
                if(s1[i]!==s1[j]) {
                    dp[i][j]=0
                }
                else {
                    if(j-i<3) { //如果长度为2,符合题意的条件是s1[i]===s1[j]
                        dp[i][j]=1
                    }
                    else {
                        dp[i][j]=dp[i+1][j-1]
                    }
                }
    
                if(dp[i][j]&&j-i+1>maxLen) {
                    maxLen = j-i+1
                    start = i
                }
            }
        }
        return(s1.slice(start,start+maxLen).join(''))
    };
    
    展开全文
  • 给定一个字符 s,找到 s 中最长回文子串。你可以假设s 的最大长度为 1000。 示例 1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2: 输入: "cbbd" 输出: "bb" 思路一:翻转字符法。...

    半对

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

    示例 1:

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

    输入: "cbbd"
    输出: "bb"

    思路一:翻转字符串法。

    1.将整个字符串反转,然后判断原始的字符串是否在反转的字符串中出现。

    2.只是出现还不够,还要验证该字符串是否是回文的。

    class Solution {
    public:
        string longestPalindrome(string s) {
            if (s.length()==1) return s;
            string rev=s;
            std::reverse(rev.begin(),rev.end());  //reverse函数,将字符串反转
            string res;
            if (rev==s) return s;
            int len=0;
            for (int i=0; i<s.length(); i++)
            {
                string tmp;
                for (int j=i; j<s.length(); j++)
                {
                    tmp=tmp+s[j];
                    if(len>tmp.length())
                        continue;
                    else if (rev.find(tmp)!=-1)
                    {
                        string q=tmp;
                        std::reverse(q.begin(),q.end());
                        if(q==tmp)
                        {
                            len=q.length();
                            res=tmp;
                        }
                    }
                    else
                        break;
                }
            }
            return res;
    
        }
    };

    思路二:动态规划法.

    1.定义一个(len, len)的二维数组,数组的(i,i)是1,因为单个字符是回文字符。

    2.如果s[i]==s[i+1],则是两个连续的字符,也构成回文。

    3.从长度为三开始扫描,如果s[i]==s[j]&&d[i+1][j-1]==1,则构成一个新的回文字符串。

    class Solution {
    public:
        string longestPalindrome(string s) {
            int len= s.length();
            if (len==0||len==1) return s;
            int start=0;
            int max=1;
            vector<vector<int>> dp(len, vector<int>(len)); //注意vector<vector<int>>的初始化。
            for (int i=0; i<len; i++)
            {
                dp[i][i]=1;
                if (i<len-1&&s[i]==s[i+1])
                    {
                        dp[i][i+1]=1;
                        max=2;
                        start=i;
                    }
            }
            for (int l=3; l<=len; l++)
            {
                for (int i=0;i+l-1<len;i++)
                {
                    int j= i+l-1;
                    if (s[i]==s[j]&&dp[i+1][j-1]==1)
                        {
                            dp[i][j]=1;
                            max=l;
                            start=i;
                        }
                }
            }
            return s.substr(start,max);
    
        }
    };

     

    展开全文
  • 动态规划最长回文子串

    万次阅读 多人点赞 2019-04-25 13:17:22
    给出一个字符S,求S的最长回文子串的长度。 样例 字符"PATZJUJZTACCBCC"的最长回文子串为"ATZJUJZTA",长度为9。         还是先看暴力解法:枚举子的两个端点i和j,...

    问题:

    给出一个字符串S,求S的最长回文子串的长度。
    

    样例

    字符串"PATZJUJZTACCBCC"的最长回文子串为"ATZJUJZTA",长度为9。
    

            还是先看暴力解法:枚举子串的两个端点i和j,判断在[i, j]区间内的子串是否回文。从复杂度上来看,枚举端点需要0(n2),判断回文需要0(n),因此总复杂度是O(n3)。终于碰到一个暴力复杂度不是指数级别的问题了!但是O(n)的复杂度在n很大的情况依旧不够看。
            可能会有读者想把这个问题转换为最长公共子序列(LCS) 问题来求解:把字符串S倒过来变成字符串T,然后对S和T进行LCS模型求解,得到的结果就是需要的答案。而事实上这种做法是错误的,因为一旦S中同时存在一个子串和它的倒序,那么答案就会出错。例如字符串S= “ABCDZJUDCBA”,将其倒过来之后会变成T = “ABCDUJZDCBA”,这样得到最长公共子串为"ABCD",长度为4,而事实上S的最长回文子串长度为1。因此这样的做法是不行的。
    动态规划解决
            令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串,是则为1,不是为0。这样根据S[i]是否等于S[j],可以把转移情况分为两类:
             ①若S[i]=S[j],那么只要S[i+1]和S[j-1]是回文子串,S[i+1]至S[j-1]就是回文子串;如果S[i+1]至S[j-1]不是回文子串,则S[i]至S[j]一定不是回文子串。
             ②若S[i]!=S[j],那S[i]至S[j]一定不是回文子串。
    由此可以写出状态转移方程
    在这里插入图片描述

    边界dp[i][i]=1,dp[i][i+1]=(S[i]==S[i+1])?1:0 。
    

            到这里还有一个问题没有解决,那就是如果按照i和j从小到大的顺序来枚举子串的两个端点,然后更新dp[i]lj],会无法保证dp[i + 1][ - 1]已经被计算过,从而无法得到正确的dp[i][i]。
             如图11-4所示,先固定i=0,然后枚举j从2开始。当求解dp[0][2]时,将会转换为dp[1][],而dp[1][1]是在初始化中得到的;当求解dp[0][3]时,将会转换为dp[1][2], 而dp[1][2]也是在初始化中得到的;当求解dp[0][4]时,将会转换为dp[1][3], 但是dp[1][3]并不是已经计算过的值,因此无法状态转移。事实上,无论对ij和j的枚举顺序做何调整,都无法调和这个矛盾,因此必须想办法寻找新的枚举方式。
            根据递推写法从边界出发的原理,注意到边界表示的是长度为1和2的子串,且每次转移时都对子串的长度减了1,因此不妨考虑按子串的长度和子串的初始位置进行枚举,即第一遍将长度为3的子串的dp值全部求出,第二遍通过第一遍结果计算出长度为4的子串的dp值…这样就可以避免状态无法转移的问题。如图11-5所示,可以先枚举子串长度L (注意: L是可以取到整个字符串的长度S.len()的),再枚举左端点i,这样右端点i+ L- 1也可以直接得到。

    在这里插入图片描述
    代码:

    #include<iostream>
    #include<string>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn=1000;
    char S[maxn];//A存序列,dp[i]存以i为结尾的连续序列的最大和
    int dp[maxn][maxn];
    int main()
    {
    	gets(S);//从下标为1开始读入
    	int len=strlen(S),ans=1;
    	memset(dp,0,sizeof(dp));
    	for(int i=0;i<len;i++)
    	{
    		dp[i][i]=1;
    		if(i<len-1)
    		{
    			if(S[i]==S[i+1])
    				{
    					dp[i][i+1]=1;
    					ans=2;//初始化时注意当前最长回文子串长度;
    				}
    		}
    	}
    	//状态转移方程
    	for(int L=3;L<=len;L++)//枚举子串长度
    		for(int i=0;i+L-1<len;i++)//枚举子串起始端点 起始端点加上子串长度(子串长度包括他
    		本身,所以要-1)必须小于总长,
    			{
    				int j=i+L-1;//子串右端点
    				if(S[i]==S[j]&&dp[i+1][j-1]==1)
    				{
    					dp[i][j]=1;
    					ans=L;//更新最长回文子串长度;
    				}
    			}
    		cout<<ans<<endl;
    }
    
    展开全文
  • 给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 注意: 假设字符串的长度不会超过 1010。 示例 1: 输入: ...
  • 目录 1. 题目描述 2. 题目分析 2.1 动态规划法 2.1.1 原理分析 ...给定一个字符 s,找到 s 中最长回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: "babad" 输...
  • 最长回文串动态规划 参考:https://writings.sh/post/algorithm-longest-palindromic-substring class Solution { public String longestPalindrome(String s) { int len = s.length(); //为了操作方便,将...
  • LeetCode 最长回文串

    2020-12-22 01:04:30
    文章目录最长回文串题目解题思路代码实现实现结果 最长回文串 题目来源:https://leetcode-cn.com/problems/longest-palindrome/ 题目 给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的...
  • 最长回文子串——动态规划

    千次阅读 2019-07-02 16:04:48
    题目: 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设s 的最大长度为 1000。...设状态dp[j][i]表示索引j到索引i的子串是否是回文串。则转移方程为: 则dp[j][i]为true时表示索引j...
  • 题目描述: ...比如,abxdba,删去x,可以得到abdba,是一个回文字符,你的任务就是求出给定的字符删去若干字符后可以得到的最长回文字符的长度。字符长度不超过1000,字符范围从'a'到'z'。...
  • 题目描述:给你一个字符s,找到s中最长回文子串。 递推式: class Solution { public: string longestPalindrome(string s) { int len=s.size(); if(len<2) return s; bool dp[len][len];//布尔型...
  • 文章目录一、题目概要二、题目理解三、解题思路 一、题目概要 给定一个字符串 s,找到 s 中最长的回文子串。...分析题目时思考用什么方法,最长回文串由一个个短回文串组成,这种利用之前的解来帮助后面的问...
  • 构造最长回文串

    2020-06-09 23:06:54
    现在我们考虑一下可以构成回文串的两种情况: 字符出现次数为双数的组合 字符出现次数为双数的组合+一个只出现一次的字符 思路: 统计字符出现的次数即可,双数才能构成回文。因为允许中间一个数单独出现,比如...
  • 一开始我是想着一维数组dp,dp[i]表示前i个字符的最长回文子串,注意这里的子串不是必须连续的,然后f发现一维的判断不了。 最起码需要两个指针然后转二维;dp[i][j] 表示i~j位置的最长回文子串,还是老样
  • 基于Python实现对求解最长回文子串的动态规划算法 1、题目    给定一个字符 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。 示例 1: 输入: "babad" 输出: "bab"...
  • 5. 最长回文子串动态规划java版

    千次阅读 2018-12-18 21:01:19
    这道回文题对我理解动态规划起到了很大的帮助,值得一做,虽然这道题动态规划的时间复杂度是O(N的平方)显然不是最优解,但是用来理解动态规划我觉得很合适。 给定一个字符 s,找到 s 中最长回文子串。你可以...
  • 预备知识: (1)在一个数轴上有两点i和j(i  证明: 因为 i  所以 i = 2m - j;...(2)回文串的对称性: ... 如图所示,A是一个从0到N的回文串,且M是回文串A的中心,那么就能推出字符串 AL[0
  • 最长回文子串之动态规划动态规划分析代码过程表述(结合代码看)代码和成果展示 动态规划分析 如何想到的 当然,你要是一个练题练得久了,自然就知道该采用动态规划,这就是 学霸手感 。不过再牛X也是从小白...
  • 最长回文子串 leetcode 5 若一个字符串是回文串,那么它的首尾元素应该相同,并且若该字符串的长度大于2,除去首尾元素后依然是回文串。 由此可得到判断是否是回文串的递推公式,P(i,j)P(i, j)P(i,j) 代表子串SiS_{...
  • 这个题目我刚做的时候用的是暴力穷举法,后来看很多人都使用了动态规划,因此我也看了动态规划的思想,重写了动态规划的代码。动态规划的思想Leecode官方说的很详细了,建议先看动态规划的思想,代码就很容易搞懂了...
  • 题目 给定一个字符串s,找到s中最长的回文子串。你可以假设s的最大长度为 1000。 示例 1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个...//单个字符是回文串 dp[i][i+1]=1 if s[i]=s[i+1];//连续两个相...
  • 假设dp[i,j]=1,表示str[i…j]是回文串,dp[i,j]=0表示str[i,j]不是回文串. if str[i] == str[j] then dp[i,j] = dp[i+1,j-1]. if str[i] != str[j] then dp[i,j] = 0. 代码: 完整代码已上传我的github,项目名DP,...
  • 问题描述 VJ原题 输入一个字符串Str,输出Str里最长回文子串的长度。 回文串:指aba、abba、cccbccc、aaaa这种左右对称的字符串。 串的子串:一个串的子串指此(字符)串中连续的一部分...使用动态规划。如果str[i][j]
  • 判断一个字符串是否是回文串 /*********************** * 判断一个字符串是否是回文串(左右对称) 单个数字默认为是 * @param str 需要进行判断的字符串 * @return 返回该整数是否为回文串 */ public ...
  • 给定一个字符s,找到s中最长回文子串。你可以假设s的最大长度为 1000。 leetcode地址 解法: /** * @param {string} s * @return {string} */ //开辟二维数组 const initialize2DArray = (w, h, val = ...
  • Longest Palindromic Substring 最长回文子串 学习笔记 1. Brute method 第一种方法:直接循环求解,o(n2)o(n^2) class Solution: def longestPalindrome(self, s): """ :type s: str :rtype: str
  • 当元素值是奇数时,需要用一个flag记录一下出现过奇数的,sum累加上奇数值-1(因为当有多个奇数出现时,不可能直接拼接成一个回文串);当元素是偶数时,sum直接累加上偶数值。在循环结束后,若flag为true,表明组成...
  • Java实现最长回文串

    万次阅读 多人点赞 2019-07-21 15:54:04
    此处,首先枚举出回文串的中心位置,然后,再在该位置上分别向左和向右扩展,记录并更新得到的最长回文串的长度。 package com.liuzhen.string_1; import java.util.Scanner; public class String...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,273
精华内容 10,909
关键字:

最长回文串动态规划