一帧数据 dedecms 工厂模式 meteor text interface sqlalchemy nlp cocos2d html5 vue状态管理 前端项目实战 oracle分页关键字 字符串中包含某个字符串 linux查看jdk安装路径 python算法 python自定义异常 javamysql java重写和重载 java的正则表达式 java查找字符串 学习java基础 java读取文件内容 java怎么安装 java接口调用 java中的泛型 linux用户管理 shell编程学习 ip隐藏 服务器系统下载 战地2单机地图 枪神传说辅助 ezcad2 苹果剪辑 图片放大软件 如何给黑白照片上色 8元秒电脑 模拟人生2夜生活 视频添加水印 平面设计软件下载 粉碎文件工具
当前位置: 首页 > 学习教程  > python

leetcode_1208. 尽可能使字符串相等

2021/2/6 23:54:11 文章标签: 测试文章如有侵权请发送至邮箱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 都只含小写英文字母。

二、解题思路

滑动窗口,先计算各个对应位置的字母ASCII码的差值,然后从左到右累计开销,如果大于最大开销则窗口左端右移,并减去原始左端的开销,同时更新最大长度。最后再次更新最大长度即可。

三、代码

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        diff = []
        for right in range(n):
            diff.append(abs(ord(t[right]) - ord(s[right])))

        left, right = 0, 0
        sums = 0
        max_length = 0
        for right in range(n):
            sums += diff[right]

            while sums > maxCost:
                max_length = max(max_length, right - left)
                sums -= diff[left]
                left += 1
        max_length = max(max_length, right - left + 1)
        return max_length


if __name__ == '__main__':
    ss = Solution()
    # s = "abcd"
    # t = "cdef"
    # cost = 3
    # s = "abcd"
    # t = "bcdf"
    # cost = 3
    s = "abcd"
    t = "bcdf"
    cost = 3
    ans = ss.equalSubstring(s, t, cost)
    print(ans)
悲恋花丶无心之人 CSDN认证博客专家 深度学习 神经网络 Pytorch
计算机视觉在读研究生,熟悉Pytorch,MXNet,TensorFlow,Keras等深度学习框架,主要涉及的领域有目标检测,语义分割,超分辨率重建,行人重识别等。
个人GitHub网址为:https://github.com/nickhuang1996

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

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?