【力扣每日一题】力扣2645构造有效字符串的最少插入数

发布时间:2024-01-11 11:59:35

题目来源

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

题目概述

给你一个字符串?word?,你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次,返回使?word?有效 需要插入的最少字母数。 如果字符串可以由 "abc" 串联多次得到,则认为该字符串?有效?

示例

示例 1:

输入:word = "b"

输出:2

解释:在 "b" 之前插入 "a" ,在 "b" 之后插入 "c" 可以得到有效字符串 "abc" 。

示例 2:

输入:word = "aaa"

输出:6

解释:在每个 "a" 之后依次插入 "b" 和 "c" 可以得到有效字符串 "abcabcabc" 。

示例3 :

输入:word = "abc"

输出:0

解释:word 已经是有效字符串,不需要进行修改。

提示

  • 1 <= word.length <= 50
  • word 仅由字母 "a"、"b" 和 "c" 组成。

思路分析

我们只需要遍历一遍字符串,计算第i个字符到第i - 1 个字符之间所缺少的字符数累计即可。

代码实现

java实现

public class Solution {
    public int addMinimum(String word) {
        // 统计插入数
        int count = 0;
        // 上一个遍历到的字符
        char last = 'c';
        for(int i = 0; i < word.length(); i++) {
            char current = word.charAt(i);
            // temp表示前面缺少的字符
            int temp = current - 1;
            if (temp < 'a') temp = 'c';
            // 前面缺少的字符一直到上一个字符需要添加多少字符
            int add = 0;
            // 如果前面要补的字符小于之前的字符
            // 说明横跨了一个abc,要补的数量前一个字符到c加上当前字符到a的数量
            if (temp < last) {
                add = 'c' - last + current - 'a';
            }else {
                //如果前面要补的字符大于等于之前的字符,要补的数量为前一个字符与最后一个要补的字符之间的数量
                add = temp - last;
            }
            count += add;
            last = current;
        }
        count += 'c' - last;
        return count;
    }
}

c++实现

class Solution {
public:
    int addMinimum(string word) {
        // 统计插入数
        int count = 0;
        // 上一个遍历到的字符
        char last = 'c';
        for(int i = 0; i < word.length(); i++) {
            char current = word[i];
            // temp表示前面缺少的字符
            int temp = current - 1;
            if (temp < 'a') temp = 'c';
            // 前面缺少的字符一直到上一个字符需要添加多少字符
            int add = 0;
            // 如果前面要补的字符小于之前的字符
            // 说明横跨了一个abc,要补的数量前一个字符到c加上当前字符到a的数量
            if (temp < last) {
                add = 'c' - last + current - 'a';
            }else {
                //如果前面要补的字符大于等于之前的字符,要补的数量为前一个字符与最后一个要补的字符之间的数量
                add = temp - last;
            }
            count += add;
            last = current;
        }
        count += 'c' - last;
        return count;
    }
}

文章来源:https://blog.csdn.net/qq_56460466/article/details/135521332
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。