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

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

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

समाधान के चरण

1. cost_f := 0
2. i := 1
3. ind := 0
4. i को 1 से len(s)-1 तक:
   • cur := s[i], c_cost := cost[i]
   • prev := s[i-1], p_cost := cost[i-1]
   • यदि ind == 1:
     • prev := prev_i, p_cost := cost_i
   • यदि cur == prev:
     • यदि c_cost >= p_cost:
       • cost_f += p_cost
       • prev_i, cost_i = 0, 0
       • ind := 0
     • यदि c_cost < p_cost:
       • cost_f += c_cost
       • ind := 1
       • prev_i, cost_i = prev, p_cost
   • अन्यथा:
     • prev_i, cost_i = 0, 0
     • ind := 0
5. cost_f वापस करें

उदाहरण

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

def solve(s, cost):
    cost_f = 0
    i = 1
    ind = 0
    prev_i, cost_i = 0, 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