【力扣】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)

简介: 【2月更文挑战第17天】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)

题目链接

题意

给你一个字符串 word ,你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次,返回使 word 有效 需要插入的最少字母数。
如果字符串可以由 "abc" 串联多次得到,则认为该字符串 有效 。
提示:
$1 <= word.length <= 50$
$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<dp[i-1]-1,所以第二个转移方程可以写为dp[i]=dp[i-1]-1
  • 上述做法的时间复杂度为$O(n)$,空间复杂度也是$O(n)$。
  • 观察代码发现其实状态转移的时候只依赖上一个状态,所以可以使用滚动数组进行优化,优化后的空间复杂度为$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;
        }
};
目录
相关文章
|
6天前
力扣740. 删除并获得点数(动态规划)
力扣740. 删除并获得点数(动态规划)
|
6天前
力扣213打家劫舍2(简单动态规划)
力扣213打家劫舍2(简单动态规划)
|
6天前
力扣198.打家劫舍(简单动态规划)
力扣198.打家劫舍(简单动态规划)
|
7天前
|
机器学习/深度学习 canal NoSQL
从C语言到C++_12(string相关OJ题)(leetcode力扣)
从C语言到C++_12(string相关OJ题)(leetcode力扣)
18 0
|
7天前
|
编译器 测试技术 C语言
从C语言到C++_11(string类的常用函数)力扣58和415(下)
从C语言到C++_11(string类的常用函数)力扣58和415
7 0
|
7天前
|
存储 编译器 C语言
从C语言到C++_11(string类的常用函数)力扣58和415(中)
从C语言到C++_11(string类的常用函数)力扣58和415
11 0
|
7天前
|
存储 C语言 C++
从C语言到C++_11(string类的常用函数)力扣58和415(上)
从C语言到C++_11(string类的常用函数)力扣58和415
11 0
|
13天前
leetcode代码记录(动态规划基础题(斐波那契数列)
leetcode代码记录(动态规划基础题(斐波那契数列)
12 0
|
13天前
|
监控 安全 Go
【Go语言专栏】Go语言中的并发性能分析与优化
【4月更文挑战第30天】Go语言以其卓越的并发性能和简洁语法著称,通过goroutines和channels实现并发。并发性能分析旨在解决竞态条件、死锁和资源争用等问题,以提升多核环境下的程序效率。使用pprof等工具可检测性能瓶颈,优化策略包括减少锁范围、使用无锁数据结构、控制goroutines数量、应用worker pool和优化channel使用。理解并发模型和合理利用并发原语是编写高效并发代码的关键。
|
13天前
|
消息中间件 算法 Java
C++实时通信优化技术探究
C++实时通信优化技术探究
25 3