kubeflow CANopen EasyCVR mobile syntax tree Egret Engine 管理后台框架 jquery获取元素宽度 flutter项目案例 linux启动mysql命令 kubernetes入门 python3文件操作 python调用方法 python文件 python中time python使用正则表达式 java使用 java数据 java学习平台 java集合遍历 jdk环境配置 java语言运算符 php开发教程 kafka中文教程 flash实例 相关软件 workflow中文 unix系统下载 rar去广告 福昕阅读器绿色版 手机知识 blued是什么软件 淘宝自动发货软件 skycc组合营销软件 用流量打电话的软件 u盘系统下载 苹果放大镜 电脑cmd命令大全 网红照片男
当前位置: 首页 > 学习教程  > python

Leetcode每日一题:1208. 尽可能使字符串相等

2021/2/7 9:55:37 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

目录问题描述思路分析及代码实现问题描述 给你两个长度相同的字符串,s 和 t。 将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销(开销可能为 0),也就是两个字符的 ASCII 码值的差的绝对值。 用于变更字符…

目录

    • 问题描述
    • 思路分析及代码实现

问题描述

给你两个长度相同的字符串,s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销(开销可能为 0),也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串,则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串,则返回 0。

示例 1:
输入:s = “abcd”, t = “bcdf”, cost = 3
输出:3
解释:s 中的 “abc” 可以变为 “bcd”。开销为3,所以最大长度为 3。

示例 2:
输入:s = “abcd”, t = “cdef”, cost = 3
输出:1
解释:s 中的任一字符要想变成 t中对应的字符,其开销都是 2。因此,最大长度为 1。 示例 3:
输入:s = “abcd”, t = “acde”, cost = 0
输出:1
解释:你无法作出任何改动,所以最大长度为 1。

提示:

1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
s 和 t 都只含小写英文字母。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/get-equal-substrings-within-budget
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路分析及代码实现

这道题要注意审题,题中有个关键词是子字符串,所以可以转化为最大区间的问题,最大区间问题可以通过滑动窗口的做法来解决
然后直接套用滑动窗口的模板即可

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        left = 0
        right = 0
        total = 0
        res = 0
        cha = []
        for i in range(len(s)):
            cha.append(abs(ord(s[i])-ord(t[i])))
        while right < len(s):
            total += cha[right]
            if total > maxCost:
                total -= cha[left]
                left += 1
            res = max(res, right-left+1)
            right += 1
        return res

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_2000211.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?