Pythonの文法規則を使用して作成できる文字列の数をカウントするプログラム

数nがあるとすると、次のルールを使用して生成できる長さnの文字列の数を見つける必要があります-

• 各文字は小文字の母音です[a、e、i、o、u]

• 「a」の後には1つの「e」のみを続けることができます

• 「e」の後には、「a」と「i」のいずれかのみを続けることができます

• 「i」の後に別の「i」を続けることはできません

• 「o」の後には、「i」と「u」のいずれかのみを続けることができます

• 「u」の後には1つの「a」のみを続けることができます

結果が非常に大きい場合は、結果を10 ^ 9+7で変更します。

したがって、入力がn =2の場合、出力は10になります。これは、次の2文字の文字列を生成できるためです：["ae"、 "ea"、 "ei"、 "ia"、 "ie"、 " io "、" iu "、" oi "、" ou "、" ua "]

これを解決するには、次の手順に従います-

• m =10 ^ 9 + 7

• nが0と同じ場合、

  • 0を返す

• 5つの変数a、e、i、o、uを定義し、最初はすべて1です

  • _の範囲が0からn-1の場合、実行

    • a：=e + i + u

    • e：=a + i

    • i：=e + o

    • o：=i

    • u：=i + o

• return（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