Chương trình đếm số chuỗi mà chúng ta có thể thực hiện bằng cách sử dụng các quy tắc ngữ pháp trong Python

Giả sử chúng ta có một số n, chúng ta phải tìm số chuỗi có độ dài n có thể được tạo ra bằng cách sử dụng các quy tắc sau -

• Mỗi ký tự là một nguyên âm viết thường [a, e, i, o, u]

• "a" chỉ có thể được theo sau bởi một "e"

• "e" chỉ có thể được theo sau bởi bất kỳ "a" và "i"

• "i" không được theo sau bởi "i" khác

• "o" chỉ có thể được theo sau bởi bất kỳ "i" và "u"

• "u" chỉ có thể được theo sau bởi một "a"

Nếu kết quả rất lớn, hãy sửa đổi kết quả bằng 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là n =2, thì đầu ra sẽ là 10, vì chúng ta có thể tạo hai chuỗi ký tự sau:["ae", "ea", "ei", "ia", "ie", " io "," iu "," oi "," ou "," ua "]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m =10 ^ 9 + 7

• nếu n giống 0 thì

  • trả về 0

• xác định năm biến a, e, i, o, u, tất cả đều là 1 ban đầu

  • đối với _ trong phạm vi 0 đến n-1, thực hiện

    • a:=e + i + u

    • e:=a + i

    • i:=e + o

    • o:=i

    • u:=i + o

• return (a + e + i + o + u) mod m

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

3

Đầu ra

19