পাইথনে একটি স্ট্রিং তিনটি প্যালিনড্রোমে ভাগ করা যায় কিনা যাচাই করার প্রোগ্রাম

আমাদের একটি স্ট্রিং s আছে। আমাদের যাচাই করতে হবে যে s-কে তিনটি প্যালিনড্রোমিক সাবস্ট্রিংয়ে ভাগ করা যায় কিনা।

উদাহরণস্বরূপ, ইনপুট s = "levelpopracecar" হলে আউটপুট হবে True কারণ এটিকে "level", "pop", "racecar"-এ ভাগ করা যায়, সবগুলো প্যালিনড্রোম।

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

• n := s-এর আকার

• dp := n x n আকারের ম্যাট্রিক্স False দিয়ে ফিল করে

• i = n-1 থেকে ০ পর্যন্ত ১ কমানো হারে লুপ চালান:

  • j = 0 থেকে n-1 পর্যন্ত লুপ চালান:

    • যদি i >= j হয়, তবে dp[i][j] := True

    • অন্যথায়, যদি s[i] == s[j] হয়, তবে dp[i][j] := dp[i+1][j-1]

• i = 1 থেকে n-1 পর্যন্ত লুপ চালান:

  • j = i+1 থেকে n-1 পর্যন্ত লুপ চালান:

    • যদি dp[0][i-1] এবং dp[i][j-1] এবং dp[j][n-1] সবগুলো True হয়, তবে True রিটার্ন করুন

• False রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

def solve(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    for i in range(n-1, -1, -1):
        for j in range(n):
            if i >= j:
                dp[i][j] = True
            elif s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1]
    for i in range(1, n):
        for j in range(i+1, n):
            if dp[0][i-1] and dp[i][j-1] and dp[j][n-1]:
                return True
    return False

s = "levelpopracecar"
print(solve(s))

ইনপুট

"levelpopracecar"

আউটপুট

True