Pythonで文字が繰り返されないようにするための最小の削除コストを見つけるプログラム

文字列sとcostという整数の別の配列があるとします。ここで、cost[i]はsのi番目の文字を削除するコストを表します。 2つの同じ文字が隣り合っていないように、削除の最小コストを見つける必要があります。選択した文字を同時に削除することに注意する必要があります。したがって、キャラクターを削除した後、他のキャラクターを削除するコストは変わりません。

したがって、入力がs ="pptpp"、cost =[2,3,4,5,2]の場合、コスト2 + 2 =4で最初と最後のpを削除すると、出力は4になります。文字列はここでは「ptp」になります。2つの同じ文字が次々に存在することはありません

これを解決するために、次の手順に従います-

• cost_f：=0
• i：=1
• ind：=0
• 範囲1からs-1のサイズのiの場合、実行
  • 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：=cost_f + p_cost
      • prev_i：=0、cost_i：=0
      • ind：=0
    • c_cost
    • cost_f：=cost_f + c_cost
    • ind：=1
    • prev_i：=prev、cost_i：=p_cost
• それ以外の場合、
  • prev_i：=0、cost_i：=0
  • ind：=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