โปรแกรมนับจำนวนสตริงที่เราสร้างได้โดยใช้กฎไวยากรณ์ใน 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"]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม. =10^9 + 7

• ถ้า n เท่ากับ 0 แล้ว

  • คืนค่า 0

• กำหนดห้าตัวแปร 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))

อินพุต

3

ผลลัพธ์

19