파이썬에서 문법 규칙을 사용하여 만들 수 있는 문자열의 수를 세는 프로그램

<시간/>

숫자 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 반환
5개의 변수 a, e, i, o, u를 정의합니다. 처음에는 모두 1입니다.
- _에 대해 범위 0에서 n-1까지, 수행
  - a :=e+i+u
  - e :=a+i
  - 나는 :=e+o
  - o :=나는
  - 유 :=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))