C++ 中获取预算内的相等子字符串

假设我们有两个长度相同的字符串 s 和 t。我们想要将 s 转换为 t。将 s 的第 i 个字符更改为 t 的第 i 个字符的成本为 |s[i] - t[i]|，即字符 ASCII 值之间的绝对差。我们还有一个整数 maxCost。我们必须找到 s 的子字符串的最大长度，该子字符串可以更改为与 t 的对应子字符串相同，且成本小于或等于 maxCost。

因此，如果输入类似于 s = “abcd” 和 t = “bcdf”，则 maxCost 将为 3，这是因为 s 中的 “abc” 可以转换为 “bcd”，其成本为 3，则输出将为 3。

为了解决这个问题，我们将遵循以下步骤：

  • j := 0，sum := 0 和 ret := 0

  • 对于 i 从 0 到 s 和 t 的最小长度

    • sum 增加 |s[i] – t[i]|

    • 当 sum > maxCost 时

      • sum 减去 |s[i] – t[i]|

      • j 增加 1

    • ret := ret 和 (i – j + 1) 的最大值

  • 返回 ret

示例 (C++)

让我们看看下面的实现，以便更好地理解：

class Solution {
public:
   int equalSubstring(string s, string t, int maxCost) {
      int j = 0;
      int sum = 0;
      int ret = 0;
      for(int i = 0; i < min((int)s.size(), (int)t.size()); i++){
         sum += abs(s[i] - t[i]);
         while(sum > maxCost){
            sum -= abs(s[j] - t[j]);
            j++;
         }
         ret = max(ret, i - j + 1);
      }
      return ret;
   }
};

输入

"abcd"
"bcdf"
3

输出

3

更新于：2020年3月31日

浏览量：145

开启您的 职业生涯

完成课程获得认证

开始
广告