数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：找出相同长度的字符串
假设我们有一个字符串 'i'，它包含小写字母，以及另一个整数 'j'。我们需要找出有多少个字符串与 'i' 的长度相同，并且在字典序上小于或等于 'i'，并且没有连续的相同字符超过 'j' 个。
答案需要通过对结果取模 10 ^ 9 + 7 来计算。
因此，如果输入像 i = "app"，j = 2，那么输出将是 405。
为了解决这个问题，我们将遵循以下步骤：
如果 j <= 0，则
返回 0
m := 10 ^ 9 + 7
n := i 的长度
nums := 一个新列表，包含 s 中每个字符的（字符的 Unicode 表示 - "a" 的 Unicode 表示）
返回 dp(0, True, -1, 0) mod m
定义一个函数 dp()。它将接收 pos、bound、last、count 作为参数
如果 count > j 不为零，则
返回 0
如果 pos 等于 n，则
返回 1
num := nums[pos]
res := 0
对于 i 从 0 到 (num + 1 如果 bound，否则 26)，执行以下操作：
res := res + dp(pos + 1, true 如果 bound 并且 i 等于 num，i, count *(true 如果 i 等于 last) + 1)
返回 res
从主方法返回 dp(0, True, -1, 0) % m
示例
让我们看一下下面的实现，以便更好地理解：
class Solution:
def solve(self, s, k):
if k <= 0:
return 0
MOD = 10 ** 9 + 7
n = len(s)
nums = [ord(char) - ord("a") for char in s]
def dp(pos, bound, last, count):
if count > k:
return 0
if pos == n:
return 1
num = nums[pos]
res = 0
for i in range(num + 1 if bound else 26):
res += dp(pos + 1, bound and i == num, i, count * (i == last) + 1)
return res
return dp(0, True, -1, 0) % MOD
ob = Solution()
print(ob.solve('app',2))输入
i = "app" j = 2
输出
405
更新于： 2020-12-23
112 次浏览
广告