730. Count Different Palindromic Subsequences 统计不同回文子序列

转载 作者：大佬之路 更新时间：2024-01-31 14:18:08 24 4

Input: 
S = 'bccb'
Output: 6
Explanation: 
The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.

Input: 
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
Output: 104860361
Explanation: 
There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.

class Solution:
    def countPalindromicSubsequences(self, S):
        """
        :type S: str
        :rtype: int
        """
        def count(S, i, j):
            if i > j: return 0
            if i == j: return 1
            if self.m_[i][j]:
                return self.m_[i][j]
            if S[i] == S[j]:
                ans = count(S, i + 1, j - 1) * 2
                l = i + 1
                r = j - 1
                while l <= r and S[l] != S[i]: l += 1
                while l <= r and S[r] != S[i]: r -= 1
                if l > r: ans += 2
                elif l == r: ans += 1
                else: ans -= count(S, l + 1, r - 1)
            else:
                ans = count(S, i + 1, j) + count(S, i, j - 1) - count(S, i + 1, j - 1)
            
            self.m_[i][j] = ans % (10 ** 9 + 7)
            return self.m_[i][j]
        
        n = len(S)
        self.m_ = [[None for _ in range(n)] for _ in range(n)]
        return count(S, 0, n - 1)

24 4 0

• java - 登录: different different files for different log levels

  我知道这类问题已经得到解答，但就我而言，我已经尝试了所有配置，但仍然不起作用。我需要对我的配置有一个新的看法(我确信我错过了一些东西)。两个附加程序都会记录所有级别 我想将所有包的信息 >= 记录到控

• optimization - 针对 ARM : Why different CPUs affects different algorithms differently (and drastically) 进行优化

  我正在对 Windows 移动设备上的代码性能进行一些基准测试，并注意到某些算法在某些主机上的表现明显更好，而在其他主机上则明显更差。当然，考虑到时钟速度的差异。 供引用的统计数据(所有结果均由同一个

• c - 奇怪的问题 : Getting different calculation results of the area and perimeter of a polyngn (on different machines and on different times)

  我有一个程序可以计算多边形的面积和周长。程序还会确认面积和周长的计算结果是否与预期结果相同。 我不明白发生了什么，但确认面积和周长是否与预期相同的验证部分无法正常工作。 例如，我现在测试并在所有情况下

• jquery - CSS3 过渡 + jQuery : translations of the x-axis have different results in different browsers for two different items

  Codepen :(对于那些想直接进入的人来说，这是一个代码笔。在 Chrome 和 IE 中尝试一下，看看结果的不同) 我正在尝试使用 css3 转换/过渡，因为它们比 jquery 效果更流畅。

• python : different regular expressions with different substitutions

  我有几个不同的正则表达式要在给定文本中匹配和替换。 regex1 :如果文本包含单词“Founder”，则将所有文本替换为首席执行官 正则表达式2:如果文本包含9位数字，则将其替换为NUM 我尝试使用

• Java邮件 : How to use different SOCKS5 for different threads?

  我编写了多线程应用程序，它从每个线程的数据库连接到一些电子邮件帐户。我知道 JavaMail 没有任何选项可以使用 SOCKS5 进行连接，因此我决定通过 System.setProperty 方法使

• iOS Storyboard : Different Layouts for Different Devices

  如您所见，这是我当前 Storyboard的不同设备预览。底部的透明绿色被另一个 View Controller 占用，但需要为每个不同的尺寸类固定间距。我尝试将 Storyboard 中的宽度和高度

• swift 2 : Different gravity to different sprites

  我正在创建一个游戏，我需要能够改变玩家 Sprite 的速度。我认为最好的选择是通过重力影响 Sprite 。为了给用户运动的感觉，我希望背景以完全相同的速度向相反的方向移动。 我怎样才能给背景一个不

• python - B树 : Is there a difference between different TreeSet incarnations?

  我正在查看BTrees库并注意到有多个 TreeSet (和其他)类，例如 BTrees.IOBTree.TreeSet BTrees.OOBTree.TreeSet BTrees.LFBTree.T

• 安卓NDK : Compiling different libraries for different architectures

  我有一个小型 C++ 库，必须为 armeabi 和 armeabi7a 编译。我还有一个非常大的 c++ 库，只需要为 armeabi 编译。现在正在为两种架构编译它们(使用 NDK)，但这使我的

• reactjs - MuiThemeProvider : How to use different themes for different routes?

  我需要根据站点的当前部分稍微更改主题。 似乎 MuiThemeProvider 只在加载时设置 muiTheme；但需要在 props 变化时更新。 如何做到这一点？ 最佳答案 您可以尝试将主题放在包

• latex 列表 : different counters for different listing environments

  如何创建两个每个都有自己的计数器的 lSTListing 环境？ 如果我使用例如 \lstnewenvironment{algorithm}[2]{ \renewcommand\lstlist

• travis-ci - 特拉维斯 : different `script` for different branch?

  我想使用 Travis-CI 和 Github 基于分支设置部署。 IE。 - 如果我们从 develop 构建- 然后执行 /deploy.rb使用 DEV 环境主机名，如果 master - 然后

• wpf - 数据绑定(bind) : Different triggers for different purposes

  我有一个带有数据验证的 WPF MVVM 数据表单窗口。很多控件都是文本框。目前，数据绑定(bind)触发器设置为默认值，即。 e.失去焦点。这意味着仅在可能完全填写字段时才对其进行验证。所以当删除一

• Xamarin 表单 : Is it normal to have different screen for different viewModel

  我有许多应用程序的内容页面，并最终为每个内容页面编写了很多 View 模型。例如。如果我有一个包含项目组的列表，我将有一个 ShowAllViewModel并绑定(bind)到内容页面和列表中单个项目

• javascript - Backbone : Different views for different tab content

  我有一个通用 View 和 4 个其他 View 。我在通用 View 中使用 Bootstrap 选项卡(导航选项卡)。我希望其他 4 个 View 成为通用 View 中 4 个选项卡的内容。由于

• maven-2 - Maven : Different configuration for different goals

  我希望针对 Maven 发布插件的不同目标有不同的配置选项。故事是这样的: 我正在将 Git 用于 SCM。我希望release:prepare插件在本地完成所有操作，并让release:perfor

• java - Java中的TableModel : how to specify different renderers for different rows?

  我正在为一个项目使用AbstractTableModel制作一个自定义TableModel，并且我需要找到一种方法让复选框显示在某些行上，而不是其他行上。我已经实现了 getColumn 方法，但我希

• JavaScript 事件循环 : Different queue for different types of events?

  摘自《Javascript 忍者的 secret 》一书: EVENTS ARE ASYNCHRONOUS Events, when they happen, can occur at unpredi

• java - GWT 记录器 : Different Levels to Different Handlers

  我正在尝试配置我的第一个 GWT 记录器，到目前为止，我已经将日志消息打印到我的 JS 控制台(FF 的 Firebug): 最终，我希望非SEVERE 消息转到consoleHa