Python में अधिकतम k कैरेक्टर हटाने के बाद पालिंड्रोम बन सकता है या नहीं, इसकी जांच करने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें जांचना है कि क्या हम अधिकतम k कैरेक्टर हटाने के बाद इस स्ट्रिंग को पालिंड्रोम बना सकते हैं या नहीं।

इसलिए, यदि इनपुट इस तरह है s = "lieuvrel", k = 4, तो आउटपुट True होगा, हम तीन कैरेक्टर हटाकर पालिंड्रोम "level" प्राप्त कर सकते हैं।

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

• lcs() फ़ंक्शन परिभाषित करें। यह a, b लेगा
• m := a का आकार, n := b का आकार
• table := (m + 1) x (n + 1) आकार का मैट्रिक्स और 0 से भरें
• i के लिए 1 से m तक रेंज में, करें
  • j के लिए 1 से n तक रेंज में, करें
    • यदि a[i - 1] b[j - 1] के समान है, तो
      • table[i, j] := 1 + table[i - 1, j - 1]
    • अन्यथा,
      • table[i, j] := table[i, j - 1] और table[i - 1, j] का अधिकतम
• table[m, n] लौटाएं
• मुख्य मेथड से निम्नलिखित करें:
• सत्य लौटाएं जब (s का आकार - lcs(s, s का रिवर्स) <= k) अन्यथा असत्य

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

उदाहरण

class Solution:
    def solve(self, s, k):
        def lcs(a, b):
            m, n = len(a), len(b)
            table = [[0] * (n + 1) for _ in range(m + 1)]
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    if a[i - 1] == b[j - 1]:
                        table[i][j] = 1 + table[i - 1][j - 1]
                    else:
                        table[i][j] = max(table[i][j - 1], table[i - 1][j])
            return table[m][n]
        return len(s) - lcs(s, s[::-1]) <= k
ob = Solution()
s = "lieuvrel"
k = 4
print(ob.solve(s, k))

इनपुट

"lieuvrel", 4

आउटपुट

True