LEETCODE 1208. Get Equal Substrings Within Budget 解题思路分析

题目大意:

尽可能使字符串相等

给你两个长度相同的字符串,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。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1208

解题思路分析:

我们可以先把两个字符串的每一位对比一下,看一下他们的差值各是多少,将每一位的差(cost)存入数组。这样问题就转化为在cost数组中找到一个最长的连续子数组,其和小于等于题目给出maxCost。这一步的处理需要用到sliding-window,初始时,sliding-window的左边和右边均在第0位,先向右移动右边扩大区间范围,并查看区间内的和,如果和小于等于maxCost,此时区间长度为一个候补解,继续向右移动右边。如果和大于maxCost,则向右移动左边,缩小区间范围,并查看区间内的和,重复以上步骤,直到数组循环结束,找到最大候补解即是答案。

看下完整实现代码:

public int equalSubstring(String s, String t, int maxCost) {
    int[] cost = new int[s.length()]; // 定义cost数组
    for(int i=0;i<s.length();i++){ // 记录字符串s和t每一位的cost差值
        cost[i] = Math.abs(s.charAt(i)-t.charAt(i));
    }
    // sum为区间和。startIndex为左边。maxLength为最大区间
    int sum=0,startIndex=0,maxLength=0;
    for(int i=0;i<s.length();i++){ // 循环cost数组
        sum+=cost[i]; // 累加当前区间总和(cost)
        if(sum<=maxCost){ // 区间总和小于等于maxCost时为一个候补解
            // 更新区间最大长度
            maxLength = Math.max(i-startIndex+1, maxLength);
        }else{ // 区间总和小于maxCost
            sum-=cost[startIndex]; // 区间和减去最左边的数字
            startIndex++; // 向右移动左边
        }
    }
    return maxLength; // 返回最大区间
}

本题解法运行时间为4ms。

Runtime: 4 ms, faster than 98.58% of Java online submissions for Get Equal Substrings Within Budget.

Memory Usage: 36.8 MB, less than 100.00% of Java online submissions for Get Equal Substrings Within Budget.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1208-get-equal-substrings-within-budget-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。