পাইথনে স্ট্রিং ভাগ করে ১ থেকে k পর্যন্ত সংখ্যার লিস্ট বানানোর উপায় গণনা

ধরুন, একটি স্ট্রিং s দেওয়া আছে যাতে শুধু ডিজিট (০-৯) আছে। আরেকটি সংখ্যা k দেওয়া আছে। আমাদের s-কে ১ থেকে k পর্যন্ত সংখ্যার একটি লিস্টে ভাগ করার ভিন্ন উপায়ের সংখ্যা বের করতে হবে। ফলাফল বড় হলে 10^9+7 দিয়ে মডুলো নিতে হবে।

উদাহরণস্বরূপ, s = "3456", k = 500 হলে আউটপুট 7। সম্ভাব্য ভাগগুলো: [3,4,5,6], [34,5,6], [3,4,56], [3,45,6], [34,56], [345,6], [3,456]।

সমাধানের ধাপসমূহ (DP)

m := 10^9 + 7, N := len(s)
dp := আকার N+1 এর অ্যারে, সব ০। dp[N] = 1 (বেস কেস)।
i = N-1 থেকে 0 পর্যন্ত লুপ চালান:
- curr_val = 0
- j = i থেকে N-1 পর্যন্ত:
  - curr_val = curr_val * 10 + int(s[j])
  - যদি 1 <= curr_val <= k হয়, তবে dp[i] = (dp[i] + dp[j+1]) % 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