Medium

题目描述

给你一个字符串 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”

解题思路

这道题的核心思路是贪心算法。我们需要理解有效字符串的规律：它必须是由多个 “abc” 子序列组成。

解题思路：

  1. 双指针方法：维护一个指向输入字符串 word 的指针 i，以及一个指向模式字符串 “abc” 的指针 j。

  2. 匹配逻辑：

    • 当 word[i] 与 “abc”[j] 匹配时，两个指针都向前移动
    • 当不匹配时，说明需要插入字符，答案加1，只移动模式指针

  3. 循环处理：模式指针使用取模运算 j % 3 来循环遍历 “abc”

  4. 边界处理：遍历完成后，如果模式指针不在起始位置（j % 3 != 0），说明当前的 “abc” 序列还未完成，需要补全剩余字符。

算法优势：

  • 贪心策略保证了最优解
  • 时间复杂度线性，空间复杂度常数
  • 代码简洁易懂

这种方法通过模拟构建过程，每次都选择当前最优的插入策略，确保最终得到最少的插入次数。

代码实现

class Solution {
public:
    int addMinimum(string word) {
        int additions = 0;
        int j = 0; // 指向 "abc" 的指针
        
        for (int i = 0; i < word.length(); i++) {
            char expected = 'a' + (j % 3);
            if (word[i] == expected) {
                j++;
            } else {
                // 需要插入字符
                additions++;
                i--; // 重新处理当前字符
            }
            j++;
        }
        
        // 如果最后一个 "abc" 序列没有完成，需要补全
        if (j % 3 != 0) {
            additions += 3 - (j % 3);
        }
        
        return additions;
    }
};

class Solution:
    def addMinimum(self, word: str) -> int:
        additions = 0
        j = 0  # 指向 "abc" 的指针
        
        i = 0
        while i < len(word):
            expected = chr(ord('a') + (j % 3))
            if word[i] == expected:
                i += 1
                j += 1
            else:
                # 需要插入字符
                additions += 1
                j += 1
        
        # 如果最后一个 "abc" 序列没有完成，需要补全
        if j % 3 != 0:
            additions += 3 - (j % 3)
        
        return additions

public class Solution {
    public int AddMinimum(string word) {
        int additions = 0;
        int j = 0; // 指向 "abc" 的指针
        
        int i = 0;
        while (i < word.Length) {
            char expected = (char)('a' + (j % 3));
            if (word[i] == expected) {
                i++;
                j++;
            } else {
                // 需要插入字符
                additions++;
                j++;
            }
        }
        
        // 如果最后一个 "abc" 序列没有完成，需要补全
        if (j % 3 != 0) {
            additions += 3 - (j % 3);
        }
        
        return additions;
    }
}

/**
 * @param {string} word
 * @return {number}
 */
var addMinimum = function(word) {
    let additions = 0;
    let j = 0; // 指向 "abc" 的指针
    
    let i = 0;
    while (i < word.length) {
        let expected = String.fromCharCode('a'.charCodeAt(0) + (j % 3));
        if (word[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)n 为字符串长度，需要遍历一次字符串
空间复杂度O(1)只使用了常数个变量

相关题目