पायथन में सबसीक्वेंस से अधिकतम पालिंड्रोम लंबाई खोजने का प्रोग्राम

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

s से कोई नॉन-एम्प्टी सबसीक्वेंस sub1 चुनें।
t से कोई नॉन-एम्प्टी सबसीक्वेंस sub2 चुनें।
sub1 और sub2 को जोड़कर स्ट्रिंग बनाएं।

हमें इस तरीके से बनने वाले सबसे लंबे पालिंड्रोम की लंबाई ढूंढनी है। अगर कोई पालिंड्रोम नहीं बन सकता, तो 0 लौटाएं।

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

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्न चरणों का पालन करेंगे:

n := s का आकार, m := t का आकार
word := s + t (दोनों स्ट्रिंग्स को जोड़ें)
dp := (n+m) x (n+m) आकार का 2D ऐरे बनाएं और 0 से भरें
i को (n + m - 1) से 0 तक घटाते हुए लूप चलाएं
- j को i से (n + m - 1) तक लूप चलाएं
  - यदि i, j के बराबर है, तो dp[i][j] := 1
  - अन्यथा यदि word[i], word[j] के बराबर है, तो dp[i][j] := 2 + dp[i+1][j-1]
  - अन्यथा, dp[i][j] := max(dp[i+1][j], dp[i][j-1])
ans := 0
i को 0 से n-1 तक लूप चलाएं
- j को m-1 से 0 तक घटाते हुए लूप चलाएं
  - यदि s[i], t[j] के बराबर है, तो ans = max(ans, dp[i][n+j])
ans लौटाएं

उदाहरण

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

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))

इनपुट

s = "hillrace", t = "cargame"