Python程序：查找避免重复字母的最小删除成本

假设我们有一个字符串s和另一个整数数组cost，其中cost[i]表示删除s中第i个字符的成本。我们必须找到最小删除成本，以确保没有两个相同的字母相邻。我们必须记住，我们将同时删除选定的字符。因此，删除一个字符后，删除其他字符的成本不会改变。

因此，如果输入类似于s = "pptpp"，cost = [2,3,4,5,2]，则输出将为4，因为如果我们移除成本为2+2 = 4的第一个和最后一个p，则字符串将变为"ptp"，这里没有两个相同的字符彼此相邻。

为了解决这个问题，我们将遵循以下步骤：

  • 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 < p_cost，则：
        • cost_f := cost_f + c_cost
        • ind := 1
        • prev_i := prev, cost_i := p_cost
    • 否则：
      • prev_i := 0, cost_i := 0
      • ind := 0
  • 返回cost_f

示例

让我们看看下面的实现以更好地理解

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

更新于：2021年10月4日

614 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告