पायथन में हानिपूर्ण रन-लेंथ एन्कोडिंग की न्यूनतम लंबाई खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक लोअरकेस स्ट्रिंग s और दूसरा मान k है। अब एक ऑपरेशन पर विचार करें जहां हम एक स्ट्रिंग पर एक रन-लेंथ एन्कोडिंग करते हैं, जिसमें बार-बार आने वाले वर्णों को एकाउंट और कैरेक्टर के रूप में रखा जाता है। तो यदि स्ट्रिंग "aaabbc" की तरह है तो उसे "3a2bc" के रूप में एन्कोड किया जाएगा। यहां हम "c" के लिए "1c" नहीं डालते हैं क्योंकि यह केवल एक बार क्रमिक रूप से प्रकट होता है। इसलिए हम पहले s में किसी भी kconsecutive वर्ण को हटा सकते हैं, फिर परिणामी रन-लेंथेनकोडिंग की न्यूनतम संभव लंबाई ज्ञात कर सकते हैं।

इसलिए, यदि इनपुट s ="xxxxxyyxxxxxzzxxx", k =2 जैसा है, तो आउटपुट 6 होगा, क्योंकि दो स्पष्ट विकल्प "yy" या "zz" को हटाना है। अगर हम "yy" को हटा दें, तो हमें "10x2z3x" मिलेगा जिसकी लंबाई 7 है। अगर हम "zz" को हटा दें, तो "5x2y8x" मिलेगा जिसकी लंबाई 6 है, यह सबसे छोटा है।

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

• कैल्क_कॉस्ट () फ़ंक्शन को परिभाषित करें। इसमें l

  . लगेगा

• अगर l, 0 के समान है, तो

  • वापसी 0

• अगर l 1 के समान है, तो

  • वापसी 1

• अन्यथा,

  • वापसी का आकार str(l) + 1

• फ़ंक्शन उपसर्ग () को परिभाषित करें। इसमें लगेगा

  • पूर्व:=जोड़ी के साथ शुरू में एक सूची [0, 0]

  • अंतिम:=शून्य

  • प्रत्येक सी इन एस के लिए, करें

    • अगर c पिछले जैसा ही है, तो

      • प्री में एक जोड़ी डालें (पूर्व के अंतिम आइटम का 0वां तत्व, पूर्व के अंतिम आइटम का 1 + पहला तत्व)

    • अन्यथा,

      • प्री में डालें (पूर्व के अंतिम आइटम का 0वां तत्व) + कैल्क_कॉस्ट (पूर्व के अंतिम आइटम का पहला तत्व, 1) प्री

    • अंतिम:=सी

  • वापसी से पहले

• मुख्य विधि से निम्न कार्य करें:

• पूर्व :=उपसर्ग (ओं)

• suf :=उपसर्ग का उल्टा(उल्टे क्रम में)

• उत्तर:=अनंत

• मैं के लिए 0 से s - k + 1 के आकार की सीमा में, do

  • जे:=मैं + के

  • जोड़ी (बाएं, मध्य):=पूर्व[i]

  • जोड़ी (दाएं, मध्य) :=suf[j]

  • लागत:=बाएँ + दाएँ

  • c1 :=s[i - 1] अगर i> 0 अन्यथा शून्य

  • c2 :=s[j] यदि j <आकार का s अन्यथा शून्य है

  • अगर c1 c2 के समान है, तो

    • लागत:=लागत + कैल्क_लागत (मध्य + मध्य)

  • अन्यथा,

    • लागत:=लागत + कैल्क_लागत (मध्य) + कैल्क_लागत (मध्य)

  • उत्तर :=न्यूनतम उत्तर और लागत

• वापसी उत्तर

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

उदाहरण

def calc_cost(l):
   if l == 0:
      return 0
   if l == 1:
      return 1
   else:
      return len(str(l)) + 1
class Solution:
   def solve(self, s, k):
      def prefix(s):
         pre = [[0, 0]]
         last = None
         for c in s:
            if c == last:
               pre.append([pre[-1][0], pre[-1][1] + 1])
            else:
               pre.append([pre[-1][0] + calc_cost(pre[-1][1]),1])
            last = c
         return pre
      pre = prefix(s)
      suf = prefix(s[::-1])[::-1]
      ans = float("inf")
      for i in range(len(s) - k + 1):
         j = i + k
         left, midl = pre[i]
         right, midr = suf[j]
         cost = left + right
         c1 = s[i - 1] if i > 0 else None
         c2 = s[j] if j < len(s) else None
         if c1 == c2:
            cost += calc_cost(midl + midr)
         else:
            cost += calc_cost(midl) + calc_cost(midr)
         ans = min(ans, cost)
         return ans
ob = Solution()
s = "xxxxxyyxxxxxzzxxx"
print(ob.solve(s, 2))

इनपुट

s = "xxxxxyyxxxxxzzxxx"

आउटपुट

6