如何用leetcode使字符串相等

本篇內容介紹了“如何用leetcode使字符串相等”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

一、題目內容

給你兩個長度相同的字符串，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)

“如何用leetcode使字符串相等”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！