โปรแกรมนับจำนวนสตริงที่สร้างได้จากกฎไวยากรณ์สระใน Python

สมมติว่าเรามีตัวเลข n ต้องหาจำนวนสตริงยาว n ที่สร้างได้จากกฎ:

• ตัวอักษรเป็นสระ [a, e, i, o, u]
• a ต้องตามด้วย e เท่านั้น
• e ตามด้วย a หรือ i
• i ไม่ตามด้วย i
• o ตามด้วย i หรือ u
• u ตามด้วย a เท่านั้น

ตัวอย่าง: n = 2 ผลลัพธ์ 10: ["ae","ea","ei","ia","ie","io","iu","oi","ou","ua"]

ขั้นตอนการแก้ปัญหา (Dynamic Programming)

1. m = 10**9 + 7
2. หาก n == 0 คืนค่า 0
3. กำหนด a = e = i = o = u = 1 (สำหรับ n=1)
4. วนลูป n-1 รอบ:
   • a, e, i, o, u = e+i+u, a+i, e+o, i, i+o (mod m)
5. คืนค่า (a+e+i+o+u) % m

ตัวอย่างโค้ด Python

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)%m, (a+i)%m, (e+o)%m, i, (i+o)%m
        return (a + e + i + o + u) % m

ob = Solution()
print(ob.solve(3))  # Output: 19

อินพุต

3

เอาต์พุต

19