পাইথনে লিস্ট বৈধ কিনা যাচাই করার প্রোগ্রাম (DP অ্যাপ্রোচ)

দেওয়া একটি সংখ্যা লিস্ট (nums) যা নিম্নলিখিত নিয়মগুলো অনুসরণ করে গ্রুপ করা যায় কিনা তা যাচাই করতে হবে:

1. সামনে থাকা জোড়া (a, a)
2. সামনে থাকা Триপলেট (a, a, a)
3. সামনে থাকা ক্রমিক Триপলেট (a, a+1, a+2)

উদাহরণ: nums = [7, 7, 3, 4, 5] → True ([7,7] এবং [3,4,5] গ্রুপ করা সম্ভব)।

ডাইনামিক প্রোগ্রামিং সমাধান

dp[i] = প্রথম iটি এলিমেন্ট ব্যবহার করে বৈধ গ্রুপিং সম্ভব কিনা।

• dp[0] = True
• প্রতিটি i (২ থেকে n) এর জন্য:
  • যদি dp[i-2] True এবং nums[i-1] == nums[i-2] হয় → dp[i] = True
  • যদি dp[i-3] True এবং (nums[i-1]==nums[i-2]==nums[i-3] বা nums[i-1]==nums[i-2]+1==nums[i-3]+2) হয় → dp[i] = True
• ফলাফল: dp[n]

পাইথন কোড

class Solution:
    def solve(self, nums):
        n = len(nums)
        dp = [True] + [False] * n
        for i in range(2, n + 1):
            if i >= 2 and dp[i - 2]:
                if nums[i - 1] == nums[i - 2]:
                    dp[i] = True
            if i >= 3 and dp[i - 3]:
                if (nums[i - 1] == nums[i - 2] == nums[i - 3]) or \
                   (nums[i - 1] == nums[i - 2] + 1 == nums[i - 3] + 2):
                    dp[i] = True
        return dp[n]

ob = Solution()
print(ob.solve([8, 8, 4, 5, 6]))  # True

টাইম কমপ্লেক্সিটি: O(n), স্পেস: O(n)।