पायथन में समान आकार के तार खोजने का कार्यक्रम

मान लीजिए, हमारे पास एक स्ट्रिंग 'i' है जिसमें लोअरकेस अक्षर और एक अन्य पूर्णांक 'j' है। हमें यह पता लगाना है कि ऐसे कितने तार हैं जो 'i' के आकार के बराबर हैं और शब्दावली की दृष्टि से छोटे या 'i' के बराबर हैं और 'j' से बड़े लगातार समान वर्ण नहीं हैं।

उत्तर की गणना मॉड को 10 ^ 9 + 7 द्वारा परिणाम खोजकर की जाती है।

इसलिए, यदि इनपुट i ="app", j =2 जैसा है, तो आउटपुट 405 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

अगर j <=0, तो
- वापसी 0
मी :=10 ^ 9 + 7
n :=मैं का आकार
nums :=एक नई सूची जिसमें s में मौजूद प्रत्येक वर्ण के लिए (वर्ण का यूनिकोड प्रतिनिधित्व - "a" का यूनिकोड प्रतिनिधित्व) शामिल है
वापसी डीपी (0, सच, -1, 0) मॉड एम
एक फ़ंक्शन को परिभाषित करें dp() । यह पॉज़, बाउंड, लास्ट, काउंट लेगा
- अगर गिनती> j गैर-शून्य है, तो
  - वापसी 0
- अगर पॉज़ n के समान है, तो
  - वापसी 1
- संख्या:=अंक [स्थिति]
- रेस :=0
- मैं के लिए 0 से (संख्या + 1 यदि बाध्य है, अन्यथा 26) की सीमा में है, तो करें
  - रेस:=रेस + डीपी (पॉज़ + 1, बाउंड होने पर सच है और मैं संख्या के समान है, i, गिनती * (सच है अगर मैं पिछले जैसा ही हूं) + 1)
- रिटर्न रेस
मुख्य विधि से वापसी dp(0, True, -1, 0) % m

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

class Solution:
   def solve(self, s, k):
      if k <= 0:
         return 0
      MOD = 10 ** 9 + 7
      n = len(s)
      nums = [ord(char) - ord("a") for char in s]
      def dp(pos, bound, last, count):
         if count > k:
            return 0
         if pos == n:
            return 1
         num = nums[pos]
         res = 0
         for i in range(num + 1 if bound else 26):
            res += dp(pos + 1, bound and i == num, i, count * (i == last) + 1)
         return res
      return dp(0, True, -1, 0) % MOD
ob = Solution()
print(ob.solve('app',2))

इनपुट

i = "app"
j = 2