题目链接
2645. 构造有效字符串的最少插入数 - 力扣（LeetCode）
解题思路 动态规划
1、定义状态d[i]为将前i个字符（为了方便编码，下标从1开始）拼凑成若干个abc所需要的最小插入数。那么初始状态d[0]=0，最终要求解d[n]，其中n为word的长度。
2、转移过程文章来源：https://www.toymoban.com/news/detail-786921.html
1、d[i] = d[i-1] + 2 当word[i]单独存在于一组abc中
2、d[i] = d[i-1] - 1 当word[i] > word[i-1],那么word[i]与word[i-1]存在同一组abc中3、因为每个字符都尽可能与前面字符组合所以情况2优于情况1文章来源地址https://www.toymoban.com/news/detail-786921.html
代码
class Solution:
def addMinimum(self, word: str) -> int:
n = len(word)
d = [0] * (n + 1)
for i in range(1,n+1):
d[i] = d[i - 1] + 2
if i > 1 and word[i-1] > word[i - 2]:
d[i] = d[i -1] - 1
return d[n]
到了这里，关于leetcode-2645 构造有效字符串的最小插入数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
