当前位置：首页 > news >正文

【LeetCode每日一题】2645. 构造有效字符串的最少插入数（计算组数+动态规划+考虑相邻字母）

news 来源：原创 2024/6/2 15:56:33

2024-1-11

文章目录

- - [2645. 构造有效字符串的最少插入数](https://leetcode.cn/problems/minimum-additions-to-make-valid-string/)
  - - - 方法一：计算组数
        方法二：动态规划
        方法三: 考虑相邻字母

2645. 构造有效字符串的最少插入数

方法一：计算组数

1.用count统计，能构成几组abc

2.如果当前字符大于之前字符，说明还在组内，不更新

3.如果当前字符小于等于之前字符,说明不是同一组的abc,组数更新

4.最终返回值：组数*3，再减去原本的字符数，就是要插入的次数

    //2645. 构造有效字符串的最少插入数---计算组数public int addMinimum2(String word) {int n = word.length();int count = 1;//最终构成abc的组数for (int i = 1; i < n; i++) {if (word.charAt(i - 1) >= word.charAt(i)) {//当前字符小于等于之前字符count++;//组数加一}}return count*3-n;//返回最终构成abc的总数-原本字符，即为要插入的次数}

方法二：动态规划

1.从1开始，d[i]为前i个字符拼成abc需要的最小插入数

2.情况一：word[i]单独存在于一组abc中，需要插两次，才能组成abc.插入次数为之前的次数+2

3.情况二：当前字符比前一个字符大，需要插一次，就可以组成abc.修改当前插入次数为：之前的次数-1，因为之前插入的两次中已经包含了当前字符。

    public int addMinimum(String word) {int n = word.length();int[] d = new int[n + 1];//d[]数组用来统计，1到n的插入次数//从1开始，d[i]为前i个字符拼成abc需要的最小插入数。for (int i = 1; i <= n; i++) {d[i] = d[i - 1] + 2;//word[i]单独存在于一组abc中，在之前情况的基础上+2. eg: a+bc / b+ac / c+abif (i > 1 && word.charAt(i - 1) > word.charAt(i - 2)) {//如果当前字符比前一个字符大，eg:ab/ ac / bcd[i] = d[i - 1] - 1;//当前字符和之前的字符在同一个abc中，重新覆盖d[i],前一个位置的插入数-1}}return d[n];}

方法三: 考虑相邻字母

1.设当前字符为x,前一个字符为y,

2.x大于y的情况：x-y-1

3.x小于等于y的情况：(x-y-1+3)mod 3 ，将计算的结果控制在0-2之间

4.开头的单独一个字符：word[0]-‘a’ ，结尾的一个字符：‘c’-word[n-1],合并为word[0]-word[n-1]+2

    public int addMinimum3(String word) {int n = word.length();int res = word.charAt(0) - word.charAt(n - 1) + 2;//合并处理开头和结尾的情况for (int i = 1; i < n; i++) {res += (word.charAt(i) - word.charAt(i - 1) + 2) % 3;}return res;}