阿里云服务器如何做两个网站,一个简单的app多少钱,学计算机好还是大数据,wordpress设置静态页面647. 回文子串
中等 相关标签 相关企业 提示 给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串#xff0c;即使…647. 回文子串
中等 相关标签 相关企业 提示 给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
示例 1 输入s “abc” 输出3 解释三个回文子串: “a”, “b”, “c” 示例 2 输入s “aaa” 输出6 解释6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
提示
1 s.length 1000s 由小写英文字母组成 思路遍历顺序 dp[i 1][j - 1] 在 dp[i][j]的左下角所以一定要从下到上从左到右遍历这样保证dp[i 1][j - 1]都是经过计算的。
代码
package __DPimport fmtfunc countSubstrings(s string) int {n : len(s)/*dp[i][j] 表示 s[i:j]是回文串*/dp : make([][]bool, n)for i : 0; i n; i {dp[i] make([]bool, n)dp[i][i] true}res : 0for i : n - 1; i 0; i-- {for j : i; j n; j {if s[i] s[j] {if i j || j-1 i {dp[i][j] true} else if j-1 0 {dp[i][j] dp[i1][j-1]}}if dp[i][j] {res}}}fmt.Println(dp)return res
}516. 最长回文子序列
中等 相关标签 相关企业 给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。 子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。
示例 1 输入s “bbbab” 输出4 解释一个可能的最长回文子序列为 “bbbb” 。 示例 2 输入s “cbbd” 输出2 解释一个可能的最长回文子序列为 “bb” 。
提示
1 s.length 1000s 仅由小写英文字母组成
代码
func longestPalindromeSubseq(s string) int {size : len(s)max : func(a, b int) int {if a b {return a}return b}dp : make([][]int, size)for i : 0; i size; i {dp[i] make([]int, size)dp[i][i] 1}for i : size - 1; i 0; i-- {for j : i 1; j size; j {if s[i] s[j] {dp[i][j] dp[i1][j-1] 2} else {dp[i][j] max(dp[i][j-1], dp[i1][j])}}}return dp[0][size-1]}
