Leetcode 1578. Minimum Deletion Cost to Avoid Repeating Letters (python)

题目

解法1：

略复杂版本的解法，一开始在contest的时候写的版本

class Solution:def minCost(self, s: str, cost: List[int]) -> int:prefix = [0]*(len(cost)+1)tmp = 0for i,num in enumerate(cost):tmp += numprefix[i+1] = tmp#print(prefix)def compute_cost(start,end):#print(start,end)return prefix[end+1]-prefix[start] - max(cost[start:end+1])ans = 0i = 0while i<len(s):curr = s[i]start = iwhile i+1<len(s) and s[i+1] == curr:i += 1end = iif end-start>=1:ans += compute_cost(start,end)i+=1return ans

one pass解法

class Solution:def minCost(self, s: str, cost: List[int]) -> int:curr_max = cost[0]curr_sum = cost[0]ans = 0curr_s = s[0]for i in range(1,len(s)):if s[i] == curr_s:curr_sum += cost[i]curr_max = max(curr_max,cost[i])#print(curr_sum,curr_max)else:ans += curr_sum - curr_maxcurr_sum = cost[i]curr_max = cost[i]curr_s = s[i]ans += curr_sum-curr_maxreturn ans