पायथन में न्यूमेरिक स्ट्रिंग को विभाजित करके मानों की सूची बनाने के तरीकों की संख्या गिनने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है। s में 0-9 के अंक हैं और हमारे पास एक अन्य संख्या k भी है। हमें उन विभिन्न तरीकों की संख्या ज्ञात करनी है जिनसे s को [1, k] की संख्याओं की सूची के रूप में दर्शाया जा सकता है। यदि उत्तर बहुत बड़ा है तो परिणाम को 10^9 + 7 से मोड करें।

इसलिए, यदि इनपुट s = "3456" k = 500 जैसा है, तो आउटपुट 7 होगा, क्योंकि हम s को इस तरह दर्शा सकते हैं: [3, 4, 5, 6], [34, 5, 6], [3, 4, 56], [3, 45, 6], [34, 56], [345, 6], [3, 456]

हल करने के चरण

m := 10^9 + 7
N := s का आकार
dp := आकार (N + 1) की सूची और 0 से भरें
dp[N] := 1
i के लिए N - 1 से 0 तक, 1 से घटाते हुए, करें
- curr_val := 0
- j के लिए i से N तक की रेंज में, करें
  - curr_val := curr_val * 10 + (s[j] संख्या के रूप में)
  - यदि curr_val, 1 से k तक की रेंज में है, तो
    - dp[i] := (dp[i] + dp[j + 1]) mod m
  - अन्यथा, लूप से बाहर निकलें
dp[0] लौटाएं

उदाहरण

class Solution:
    def solve(self, s, k):
        m = 10 ** 9 + 7
        N = len(s)
        dp = [0] * (N + 1)
        dp[N] = 1
        for i in range(N - 1, -1, -1):
            curr_val = 0
            for j in range(i, N):
                curr_val = curr_val * 10 + int(s[j])
                if 1 <= curr_val <= k:
                    dp[i] = (dp[i] + dp[j + 1]) % m
                else:
                    break
        return dp[0]

ob = Solution()
s = "3456"
k = 500
print(ob.solve(s, k))

इनपुट

"3456", 500