पायथन में बाद के चरणों से अधिकतम पैलिंड्रोम लंबाई खोजने का कार्यक्रम

मान लीजिए कि हमारे पास दो तार हैं, s और t। हम निम्नलिखित तरीके से एक स्ट्रिंग बनाना चाहते हैं -

एस से कुछ गैर-रिक्त अनुवर्ती उप 1 चुनें।
टी से कुछ गैर-रिक्त अनुवर्ती उप 2 चुनें।
स्ट्रिंग बनाने के लिए सब1 और सब2 को संयोजित करें।

हमें सबसे लंबे पैलिंड्रोम की लंबाई का पता लगाना है जिसे वर्णित तरीके से बनाया जा सकता है। अगर हम कोई पैलिंड्रोम नहीं बना सकते हैं, तो 0.

इसलिए, यदि इनपुट s ="हिलरेस" t ="कारगेम" जैसा है, तो आउटपुट 7 होगा क्योंकि हम s से "रेस" और r से "कार" ले सकते हैं, इसलिए "रेसकार" लंबाई 7 के साथ पैलिंड्रोम है ।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n :=s का आकार, m :=t का आकार
शब्द:=एस + टी
dp :=आकार (n+m) x (n+m) का 2D सरणी बनाएं और 0
से भरें
i के लिए (n + m -1) से 0 की सीमा में, 1 से घटाएं, करें
- j के लिए i से n + m-1 की श्रेणी में, करें
  - अगर मैं j के समान हूं, तो
    - डीपी [आई, जे]:=1
  - अन्यथा जब शब्द [i] शब्द [j] के समान हो, तब
    - dp[i, j] :=2 + dp[i + 1, j-1]
  - अन्यथा,
    - dp[i, j] =अधिकतम dp[i + 1, j] और dp[i, j-1]
उत्तर :=0
मैं के लिए 0 से n -1 की सीमा में, करो
- j के लिए m - 1 से -1 की श्रेणी में, 1 से घटाएं, करें
  - यदि s[i] t[j] के समान है, तो
    - ans =अधिकतम ans और dp[i, n + j]
वापसी उत्तर

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें

def solve(s, t):
   n, m = len(s), len(t)
   word = s + t
   dp = [[0] * (n + m) for _ in range(n + m)]

   for i in range(n + m - 1, -1,-1):
      for j in range(i, n + m):
         if i == j:
            dp[i][j] = 1
         elif word[i] == word[j]:
            dp[i][j] = 2 + dp[i + 1][j - 1]
         else:
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
   ans = 0
   for i in range(n):
      for j in range(m - 1, -1, -1):
         if s[i] == t[j]:
            ans = max(ans, dp[i][n + j])
   return ans

s = "hillrace"
t = "cargame"
print(solve(s, t))

इनपुट

[[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]