题目链接
题意
给你一个字符串 word ，你可以向其中任何位置插入 “a”、“b” 或 “c” 任意次，返回使 word 有效 需要插入的最少字母数。 如果字符串可以由 “abc” 串联多次得到，则认为该字符串 有效 。 提示：
1
<
=
w
o
r
d
.
l
e
n
g
t
h
<
=
50
1 <= word.length <= 50
1<=word.length<=50
w
o
r
d
word
word 仅由字母 “a”、“b” 和 “c” 组成。
思路
dp[i]表示前i个字符构成有效字符串的最小插入数，下标从1开始
初始化为dp[0]=0表示前0个字符构成有效字符串最小需要插入0个字符最终答案为dp[len(word)]转移过程：
第i个字符单独属于一个abc里，需要插入的字符数就是2，转移方程为dp[i]=dp[i-1]+2如果第i个字符可以跟第i-1个字符属于一个abc，也就是满足word[i]>word[i-1]，需要插入的字符数就是-1，即前面可以少插入一个字符，转移方程为dp[i] = min(dp[i], dp[i-1]-1) 贪心的考虑，每个字符都优先跟前面的字符去组合，而且dp[i-1]+2 O ( n ) O(n) O(n)，空间复杂度也是 O ( n ) O(n) O(n)。观察代码发现其实状态转移的时候只依赖上一个状态，所以可以使用滚动数组进行优化，优化后的空间复杂度为 O ( 1 ) O(1) O(1) 代码 普通版本golang代码 func addMinimum(word string) int { //dp[i]表示前i个字符构成有效字符串的最小插入数 dp := make([]int, len(word)+2) for i := 1; i <= len(word); i++ { dp[i] = dp[i-1] + 2 if i > 1 && word[i-1] > word[i-2] { dp[i] = dp[i-1] - 1 //dp[i] = min(dp[i], dp[i-1]-1) } } return dp[len(word)] } 普通版本c++代码 class Solution { public: int addMinimum(string word) { int n = word.size(); int dp[n+1]; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ dp[i] = dp[i-1]+2; if(i>1&&word[i-1]>word[i-2]){ dp[i] = dp[i-1]-1; } } return dp[n]; } }; 滚动数组版本golang代码 func addMinimum(word string) int { ans, las := 0, 0 for i := 1; i <= len(word); i++ { ans = las + 2 if i > 1 && word[i-1] > word[i-2] { ans = las - 1 } las = ans } return ans } 滚动数组版本c++代码 class Solution { public: int addMinimum(string word) { int ans=0; int las= 0; for (int i = 1; i <= word.size(); i++) { ans = las + 2; if (i > 1 && word[i-1] > word[i-2]) { ans = las - 1; } las = ans; } return ans; } }; 文章来源
您阅读本篇文章共花了：
发表评论