पायथन में व्याकरण नियमों का उपयोग करके बनाई जा सकने वाली स्ट्रिंग्स की संख्या गिनने का प्रोग्राम

मान लीजिए हमारे पास एक संख्या 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 लौटाएं।

• पांच वेरिएबल a, e, i, o, u को 1 से आरंभ करें।

• n-1 बार लूप चलाएं:

  • a, e, i, o, u = e+i+u, a+i, e+o, i, i+o (मोड m के साथ)।

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