Python程序：计算使用语法规则可以生成的字符串数量

假设我们有一个数字n，我们需要找到可以使用以下规则生成的长度为n的字符串数量：

  • 每个字符都是小写元音字母 [a, e, i, o, u]

  • "a" 之后只能跟一个 "e"

  • "e" 之后只能跟 "a" 或 "i"

  • "i" 之后不能再跟 "i"

  • "o" 之后只能跟 "i" 或 "u"

  • "u" 之后只能跟一个 "a"

如果结果非常大，则将结果模 10^9 + 7。

因此，如果输入是 n = 2，则输出将为 10，因为我们可以生成以下两个字母的字符串：["ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou", "ua"]

为了解决这个问题，我们将遵循以下步骤：

  • m = 10^9 + 7

  • 如果 n 等于 0，则

    • 返回 0

  • 定义五个变量 a、e、i、o、u，初始值都为 1

    • 对于范围为 0 到 n-1 的 _，执行：

      • a := e + i + u

      • e := a + i

      • i := e + o

      • o := i

      • u := i + o

  • 返回 (a + e + i + o + u) mod m

让我们来看下面的实现，以便更好地理解：

示例

在线演示

class Solution:
   def solve(self, n):
      m = (10 ** 9 + 7)
      if n == 0:
         return 0
      a = e = i = o = u = 1
      for _ in range(n-1):
         a, e, i, o, u = e+i+u, a+i, e+o, i, i+o
      return (a + e + i + o + u) % m

ob = Solution()
print(ob.solve(3))

输入

3

输出

19

更新于：2020年10月8日

187 次浏览

开启您的职业生涯

通过完成课程获得认证

开始学习
广告