Lintcode 738.Count Different Palindromic Subsequences go

/**
738 · 计数回文子序列
算法
Hard
Accepted Rate
34%

DescriptionSolutionNotesDiscussLeaderboard
Description
给出一个字符串 S, 计算字符串 S 中不同非空回文子序列的数量, 返回这个数对 10^9 + 7 取模后得结果.
字符串 S 的子序列可以通过删去 S 中 0 个或多个字符得到. 一个序列如果是回文的, 那么它逆序后与原序列相等.
两个序列 A[1], A[2], … B[1], B[2], … 如果存在 A[i] != B[i], 那么这两个序列是不同的.

S 长度的范围为 [1, 1000].
S 中所有的字符 S[i] 均来自集合 {‘a’, ‘b’, ‘c’, ‘d’}.

Example
样例 1:

输入：“bccb”
输出：6
解释：
6 个不同的非空回文子序列为 “b”, “c”, “bb”, “cc”, “bcb”, “bccb”.
注意 bcb 只计一次, 即使它出现了两次
样例 2:

输入：“abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba”
输出：104860361
解释：
字符串 S 有3104860382个不同的非空回文子序列, 对 10^9 + 7 取模后得 104860361
Tags
Company
领英

https://www.cnblogs.com/beiyeqingteng/p/11206410.html

https://www.lintcode.com/problem/738/
*/

package main/*** @param str: a string S* @return: the number of different non-empty palindromic subsequences in S*/ func countPalindSubseq(str string) int {// write your code herevar md int = 1e9 + 7if str == "" {return 0}var n int = len(str)if n <= 0 {return 0}var dp [][]int = make([][]int, n)for i := 0; i < n; i++ {dp[i] = make([]int, n)dp[i][i] = 1}for dis := 1; dis < n; dis++ {for i := 0; i < n - dis; i++ {var j int = i + disif str[i] == str[j] {var low = i + 1var high = j - 1for {if low > high || str[low] == str[j] {break}low += 1}for {if low > high || str[high] == str[j] {break}high -= 1}if low > high {dp[i][j] = 2*dp[i+1][j-1] + 2} else if low == high {dp[i][j] = 2*dp[i+1][j-1] + 1} else {dp[i][j] = 2*dp[i+1][j-1] - dp[low+1][high-1]}} else {dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]}if dp[i][j] < 0 {dp[i][j] += md} else {dp[i][j] %= md}}}return dp[0][n-1] }

总结

以上是生活随笔为你收集整理的Lintcode 738.Count Different Palindromic Subsequences go的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。