পাইথনে দীর্ঘতম প্যালিনড্রোমিক সাবস্ট্রিং

ধরুন আমাদের একটি স্ট্রিং S আছে। আমাদের S-তে দীর্ঘতম প্যালিনড্রোমিক সাবস্ট্রিং খুঁজে বের করতে হবে। আমরা ধরে নিচ্ছি যে S স্ট্রিংটির দৈর্ঘ্য 1000। তাই যদি স্ট্রিংটি "BABAC" হয় , তারপর দীর্ঘতম প্যালিনড্রোমিক সাবস্ট্রিং হল "BAB"৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব

• স্ট্রিং এর দৈর্ঘ্যের মতই এক বর্গ ম্যাট্রিক্সের ক্রম সংজ্ঞায়িত করুন এবং এটি False দিয়ে পূরণ করুন
• প্রধান তির্যক উপাদানগুলিকে সত্য হিসাবে সেট করুন, তাই DP[i, i] =0 থেকে ক্রম পর্যন্ত সমস্ত i-এর জন্য সত্য - 1
• শুরু :=0
• l এর জন্য রেঞ্জ 2 থেকে S + 1
  এর দৈর্ঘ্য
  • আমি 0 থেকে S – l + 1
    এর দৈর্ঘ্যের মধ্যে
    • শেষ :=i + l
    • যদি l =2, তাহলে
      • যদি S[i] =S[শেষ - 1], তাহলে
        • DP[i, end - 1] =True, max_len :=l, এবং শুরু :=i
    • অন্যথায়
      • যদি S[i] =S[end - 1] এবং DP[i + 1, end - 2], তাহলে
        • DP[i, end - 1] =True, max_len :=l, এবং শুরু :=i
• সূচী সূচনা থেকে শুরু + max_len এর একটি সাবস্ট্রিং ফেরত দিন

উদাহরণ(পাইথন)

আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −

class Solution(object):
   def longestPalindrome(self, s):
      dp = [[False for i in range(len(s))] for i in range(len(s))]
      for i in range(len(s)):
         dp[i][i] = True
      max_length = 1
      start = 0
      for l in range(2,len(s)+1):
         for i in range(len(s)-l+1):
            end = i+l
            if l==2:
               if s[i] == s[end-1]:
                  dp[i][end-1]=True
                  max_length = l
                  start = i
            else:
               if s[i] == s[end-1] and dp[i+1][end-2]:
                  dp[i][end-1]=True
                  max_length = l
                  start = i
      return s[start:start+max_length]
ob1 = Solution()
print(ob1.longestPalindrome("ABBABBC"))

ইনপুট

"ABBABBC"

আউটপুট

"BBABB"