【Py/Java/C++三种语言详解】LeetCode每日一题240111【贪心】LeetCode2645、构造有效字符串的最少插入数

发布时间:2024年01月11日

题目链接

LeetCode2645、构造有效字符串的最少插入数

题目描述

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

解题思路

这道题乍一看很简单,仔细一想又容易混乱,写出又臭又长的if-else嵌套代码,维护性很差。比如

class Solution:
    def addMinimum(self, word: str) -> int:
        ans = 0
        word = "c" + word + "a"
        n = len(word)
        if n == 3:
            return 2
        # 分别考虑前后位置是否需要插入
        for i in range(1, n-1):
            ch = word[i]
            if ch == "a":
                if word[i+1] == "a":
                    ans += 2
                elif word[i+1] == "c":
                    ans += 1
            elif ch == "b":
                if word[i+1] != "c":
                    ans += 1
                if word[i-1] != "a":
                    ans += 1
            elif ch == "c":
                if word[i-1] == "c":
                    ans += 2
        return ans

贪心地思考这个问题,如果我们发现相邻字符之间并不有效,即不属于"ab""bc""ca"中的任意一种,则必然要在这两个字符串之间进行字符的插入。

考虑原字符串中相邻的两个字符word[i+1]word[i],并同时考虑它们的ASCII码值差ord(word[i+1])-ord(word[i])。一共有三种可能的情况:

  • "aa","bb","cc":需要在中间补2个字符,码值差 mod 3 后为0
  • "ba","cb","ac":需要在中间补1个字符,码值差 mod 3 后为2
  • "ab","bc","ca":需要在中间补0个字符,码值差 mod 3 后为1

为了使得码值差 mode 3 后得到的结果(0,2,1)可以映射上所需补充的字符数(2,1,0),可以构建出答案增量为(ord(word[i+1]) - ord(word[i]) + 2) % 3

此外,发现上述过程由于要考虑相邻的两个字符,对第一个字符和最后一个字符需要额外讨论。为了避免这种分类讨论,一个小技巧是在word的最前面补一个"c",在word的最后面补一个"a",则可以令边界处首尾两个字符也遵循上述贪心过程。

Python

# 贪心:O(N)
class Solution:
    def addMinimum(self, word: str) -> int:
        # 小技巧,在word最前面补一个"c",最后面补一个"a"
        # 这样可以使得边界处也遵循后面遍历的规律
        word = "c" + word + "a"
        ans = 0
        # 贪心地考虑相邻的两个字符word[i+1]和word[i],
        # 并同时考虑ASCII码值差ord(word[i+1])-ord(word[i])
        # 一共有三种可能的情况:
        # "aa","bb","cc":需要在中间补2个字符,码值差 mod 3 后为0
        # "ba","cb","ac":需要在中间补1个字符,码值差 mod 3 后为2
        # "ab","bc","ca":需要在中间补0个字符,码值差 mod 3 后为1
        # 为了使得码值差模3后得到的结果(0,2,1)可以映射上所需补充的字符数(2,1,0)
        # 可以构建出答案增量为 (ord(word[i+1]) - ord(word[i]) + 2) % 3
        for i in range(0, len(word)-1):
            ans += (ord(word[i+1]) - ord(word[i]) + 2) % 3
        return ans

Java

public class Solution {
    public int addMinimum(String word) {
        word = "c" + word + "a";
        int ans = 0;
        for (int i = 0; i < word.length() - 1; i++) {
            ans += (word.charAt(i + 1) - word.charAt(i) + 2) % 3;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int addMinimum(string word) {
        word = 'c' + word + 'a';
        int ans = 0;
        for (int i = 0; i < word.length() - 1; i++) {
            ans += (word[i + 1] - word[i] + 2) % 3;
        }
        return ans;
    }
};

时空复杂度

时间复杂度:O(N)

空间复杂度:O(1)


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

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