पायथन में अक्षरों को दोहराने से बचने के लिए न्यूनतम विलोपन लागत खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक स्ट्रिंग s और पूर्णांकों की एक अन्य सरणी है जिसे लागत कहा जाता है जहां लागत [i] s में ith वर्ण को हटाने की लागत का प्रतिनिधित्व करती है। हमें विलोपन की न्यूनतम लागत का पता लगाना होगा जैसे कि एक दूसरे के बगल में दो समान अक्षर न हों। हमें यह ध्यान रखना होगा कि हम उसी समय चुने हुए पात्रों को हटा देंगे। इसलिए एक चरित्र को हटाने के बाद, अन्य पात्रों को हटाने की लागत नहीं बदलेगी।

इसलिए, यदि इनपुट s ="pptpp", लागत =[2,3,4,5,2] जैसा है, तो आउटपुट 4 होगा क्योंकि यदि हम लागत 2+2 =4 के साथ पहले और अंतिम p को हटाते हैं, तो स्ट्रिंग "ptp" होगी यहाँ कोई भी दो समान वर्ण एक के बाद एक मौजूद नहीं हैं

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

• cost_f :=0
• मैं :=1
• इंड:=0
• i के लिए 1 से लेकर s-1 के आकार तक के लिए
  • वक्र:=s[i], c_cost:=लागत[i]
  • पिछला :=s[i-1], p_cost :=cost[i-1]
  • यदि ind 1 के समान है, तो
    • पिछला :=prev_i, p_cost :=cost_i
  • यदि वक्र पिछले के समान है, तो
    • यदि c_लागत>=p_लागत है, तो
      • cost_f :=cost_f + p_cost
      • prev_i :=0, cost_i :=0
      • इंड:=0
    • यदि c_लागत
    • cost_f :=cost_f + c_cost
    • इंड:=1
    • prev_i :=पिछला, cost_i :=p_cost
• अन्यथा,
  • prev_i :=0, cost_i :=0
  • इंड:=0

उदाहरण

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

def solve(s, cost):
   cost_f = 0
   i = 1
   ind = 0

   for i in range(1, len(s)):
      cur, c_cost = s[i], cost[i]
      prev, p_cost = s[i-1], cost[i-1]
      if ind == 1:
         prev, p_cost = prev_i, cost_i

      if cur == prev:
         if c_cost >= p_cost:
            cost_f += p_cost
            prev_i, cost_i = 0,0
            ind = 0

         if c_cost < p_cost:
            cost_f += c_cost
            ind = 1
            prev_i, cost_i = prev, p_cost

      else:
         prev_i, cost_i = 0,0
         ind = 0
   return cost_f

s = "pptpp"
cost = [2,3,4,5,2]
print(solve(s, cost))

इनपुट

"pptpp", [2,3,4,5,2]

आउटपुट

4