寻找最小删除成本以避免Python中重复字母的程序

• Z时代
• 2024-01-10
• 分类：综合

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

因此，如果输入类似于 s = "pptpp", cost = [2,3,4,5,2]，那么输出将为 4，因为如果我们删除第一个和最后一个 p，成本为 2+2 = 4，则字符串将是“ptp”，这里没有两个相同的字符一个接一个出现

示例

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

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

以上是 寻找最小删除成本以避免Python中重复字母的程序 的全部内容， 来源链接： utcz.com/z/343749.html