在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（如果绑定，则为 26）内迭代
  - res := res + dp(pos + 1，如果绑定且 i 与 num 相同，则为真，否则为 26)， count * (i 等于 last的值为 true) + 1)
- 返回 res
从主方法返回 dp(0，True，-1,0) % m

更多Python相关文章，请阅读：Python 教程

示例

让我们看以下实现以更好地理解 −

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))