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

開啟您的 職業生涯

完成課程獲得認證

開始
廣告