題目鏈接
2645. 構(gòu)造有效字符串的最少插入數(shù) - 力扣（LeetCode）
解題思路 動(dòng)態(tài)規(guī)劃
1、定義狀態(tài)d[i]為將前i個(gè)字符（為了方便編碼，下標(biāo)從1開始）拼湊成若干個(gè)abc所需要的最小插入數(shù)。那么初始狀態(tài)d[0]=0，最終要求解d[n]，其中n為word的長(zhǎng)度。
2、轉(zhuǎn)移過程文章來源：http://www.zghlxwxcb.cn/news/detail-786921.html
1、d[i] = d[i-1] + 2 當(dāng)word[i]單獨(dú)存在于一組abc中
2、d[i] = d[i-1] - 1 當(dāng)word[i] > word[i-1],那么word[i]與word[i-1]存在同一組abc中3、因?yàn)槊總€(gè)字符都盡可能與前面字符組合所以情況2優(yōu)于情況1文章來源地址http://www.zghlxwxcb.cn/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]
到了這里，關(guān)于leetcode-2645 構(gòu)造有效字符串的最小插入數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
