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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告