【LeetCode】尽可能使字符串相等

HQ数字卡

关注

发布于: 2021 年 02 月 05 日

今天的每日一题，依然是滑动窗口的应用，看来 LeetCode 2 月就是滑动窗口月了。

题目

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

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

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

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

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

代码

public class DayCode {    public static void main(String[] args) {        String s = "abcd", t = "bcdf";        int maxCost = 3;        int ans = new DayCode().equalSubstring(s, t, maxCost);        System.out.println("ans is " + ans);    }
    /**     * https://leetcode-cn.com/problems/get-equal-substrings-within-budget/     * @param s     * @param t     * @param maxCost     * @return     */    public int equalSubstring(String s, String t, int maxCost) {        int n = s.length();        int[] diff = new int[n];        for (int i = 0; i < n; i++) {            diff[i] = Math.abs(s.charAt(i) - t.charAt(i));        }        int maxLength = 0;        int start = 0, end = 0;        int sum = 0;        while (end < n) {            sum += diff[end];            while (sum > maxCost) {                sum -= diff[start];                start++;            }            maxLength = Math.max(maxLength, end - start + 1);            end++;        }        return maxLength;    }}

复制代码

总结

上述代码的时间复杂度是 O(n), 空间复杂度是 O(n)
我做这个题目的时候，刚开始是没有想到滑动窗口的解决思路的。是看了题目的提示之后，才想到用滑动窗口来解决这样的问题。还是需要多总结，多练习！

发布于: 2021 年 02 月 05 日阅读数: 14

原文链接:【http://xie.infoq.cn/article/a40ccf473cfd74c2f19dc5fbc】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】尽可能使字符串相等

题目

代码

总结

HQ数字卡

评论