首页 > 其他分享 >代码随想录day46 || 647 回文子串, 516 最长回文子序列

代码随想录day46 || 647 回文子串, 516 最长回文子序列

时间:2024-08-31 10:48:43浏览次数:10  
标签:int 随想录 maxlen 647 最长 dp 回文

647 回文字串

image

func countSubstrings(s string) int {
	// 动规五部曲
	// dp[i][j] 表示s[i: j+1] 区间是否是一个回文
	// if s[i] == s[j] {if i-j <= 1 || dp[i+1][j-1] == true { dp[i][j] == true}}
	// 初始化为false
	// 从下往上,从左往右
	// print

	var count int
	var dp = make([][]bool, len(s))
	for i, _ := range dp {
		dp[i] = make([]bool, len(s))
	}

	for i:=len(s)-1; i>=0; i-- {
		for j:=i; j<len(s); j++ {
			if s[i] == s[j]{
				if j-i<=1 || dp[i+1][j-1] == true {
					dp[i][j] = true
					count++
				}
			}

		}
	}
	//fmt.Println(dp)
	return count
}

516 最长回文子序列

func longestPalindromeSubseq(s string) int {
	// 647 回文字串变体,只用统计最长字串即可
	// dp[i][j] 表示s[i: j+1] 最长回文子串长度
	// s[i] != s[j] {dp[i][j] = max(dp[i+1][j-1], dp[i+1][j], dp[i][j-1])} // 删除i, 删除j, 两个都删除
	// s[i] == s[j] {dp[i+1][j-1] + 2} // 去除首位之后的最长字串 + 两个字符长度
	// 初始化为0 , 多初始化一行一列
	// 递推来自三个方向,左下,左,下,所以遍历顺序从下往上,从左往右
	// print

	var maxlen int
	var dp = make([][]int, len(s) + 1)
	for i, _ := range dp {
		dp[i] = make([]int, len(s) + 1)
	}

	for i:=len(s); i>=0; i-- {
		for j:=i; j<len(s); j++ {
			if s[i] == s[j]{
				if i == j {
					dp[i][j+1] = dp[i+1][j] + 1
				}else {
					dp[i][j+1] = dp[i+1][j] + 2
				}
			} else {
				dp[i][j+1] = max(dp[i+1][j], max(dp[i+1][j+1], dp[i][j]))
			}
			if dp[i][j+1] > maxlen {
				maxlen = dp[i][j+1]
			}
		}
	}
	//fmt.Println(dp)
	return maxlen
}

标签:int,随想录,maxlen,647,最长,dp,回文
From: https://www.cnblogs.com/zhougongjin55/p/18389962

相关文章

  • 代码随想录算法day4 - 链表2
    题目124.两两交换链表中的节点给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。示例1:输入:head=[1,2,3,4]输出:[2,1,4,3]示例2:输入:head=[]输出:[]示例3:输入:head=[1]输出:[1]......
  • 代码随想录算法训练营,8月30日 | 203.移除链表元素, 707.设计链表, 206.反转链表
    链表理论基础1.单链表:数据域和指针域(指向下一个结点的位置)组成,头结点,结尾为空指针;双链表:多了一个指向前一个结点的指针;循环链表:结尾指向头结点。2.链表在内存中的存储不是顺序的,跟数组不同,要找一个数据只能通过前一个数据来找,所有这就导致链表的查询比数组麻烦,但是插入删除数据......
  • 5_最长回文子串
    5_最长回文子串【问题描述】给你一个字符串s,找到s中最长的回文子串。示例:输入:s="babad"输出:"bab"解释:"aba"同样是符合题意的答案。【算法设计思想】本题主要使用到了动态规划的算法思想。其程序的大致执行过程如下:首先,我们先求取下该字符串的长度,然后判断下这个字......
  • 「代码随想录算法训练营」第四十九天 | 图论 part7
    目录最小生成树的解题prim算法举例说明(来自代码随想录)题目:53.寻宝Kruskal算法举例说明(来自代码随想录)题目:53.寻宝最小生成树的解题最小生成树类型的题目主要用于解决所有节点的最小连通子图的问题,即:以最小的成本(边的权值)将图中所有节点链接到一起。最小生成树可以使用prim算......
  • 代码随想录day45 || 115 不同子序列, 583 两个字符串删除操作, 72 编辑距离
    115不同子序列funcnumDistinct(sstring,tstring)int{ //动态规划,思考一下判断连续和不连续的区别,如果相等都是左上角+1,如果不等,连续情况就是直接等于左上角,不连续情况直接归零 //dp[i][j]表示s[i]中存在t[j]结尾的的个数 //递推公式,不要求连续字串,所以,如果s[i......
  • 代码随想录算法day3 - 链表1
    题目1203.移除链表元素给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。示例1:输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]示例2:输入:head=[],val=1输出:[]示例3:输入:head=[7,7,7,7],v......
  • 代码随想录算法训练营,29日 | 704. 二分查找,27. 移除元素,977.有序数组的平方,209.长度最
    数组基础文档讲解︰代码随想录(programmercarl.com)1.连续空间、相同类型元素2.元素只能覆盖3.二维数组的地址连续吗(C++连续,Java不连续)704.二分查找题目链接:704.二分查找文档讲解︰代码随想录(programmercarl.com)视频讲解︰二分查找日期:2024-08-29思路:第一反应是想到二分查......
  • 代码随想录算法day2-数组2
    题目1209.长度最小的子数组给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的子数组[numsl,numsl+1,...,numsr-1,numsr],并返回其长度。如果不存在符合条件的子数组,返回0。示例1:输入:target=7,nums=[2,......
  • 代码随想录day44 || 1143 最长公共子序列, 1035 不相交的线, 53 最大子序列和, 392 判
    1143最长公共子序列funclongestCommonSubsequence(text1string,text2string)int{ //思路和判断最长公共数组一样 //dp[i][j]表示以text1[i],text2[j]为结尾的最长公共子序列的长度 //iftext1[i]==text2[j]{dp[i+1][j+1]=dp[i][j]+1}else{dp[i+1][j+1]=......
  • 代码随想录算法训练营第四十三天 | 300.最长递增子序列 , 674. 最长连续递增序列 , 718.
    目录300.最长递增子序列 思路1.dp[i]的定义2.状态转移方程3.dp[i]的初始化4.确定遍历顺序 5.举例推导dp数组方法一:动态规划方法二:贪心心得收获 674.最长连续递增序列思路动态规划1.确定dp数组(dptable)以及下标的含义2.确定递推公式3.dp数组如何初始化4.......