如何用leetcode使字符串相等

本篇內(nèi)容介紹了“如何用leetcode使字符串相等”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

一、題目?jī)?nèi)容

給你兩個(gè)長(zhǎng)度相同的字符串，s 和 t。

將 s 中的第 i 個(gè)字符變到 t 中的第 i 個(gè)字符需要 |s[i] - t[i]| 的開銷（開銷可能為 0），也就是兩個(gè)字符的 ASCII 碼值的差的絕對(duì)值。

用于變更字符串的最大預(yù)算是 maxCost。在轉(zhuǎn)化字符串時(shí)，總開銷應(yīng)當(dāng)小于等于該預(yù)算，這也意味著字符串的轉(zhuǎn)化可能是不完全的。

如果你可以將 s 的子字符串轉(zhuǎn)化為它在 t 中對(duì)應(yīng)的子字符串，則返回可以轉(zhuǎn)化的最大長(zhǎng)度。

如果 s 中沒有子字符串可以轉(zhuǎn)化成 t 中對(duì)應(yīng)的子字符串，則返回 0。

示例 1：

輸入：s = "abcd", t = "bcdf", cost = 3
輸出：3
解釋：s 中的 "abc" 可以變?yōu)?"bcd"。開銷為 3，所以最大長(zhǎng)度為 3。

示例 2：

輸入：s = "abcd", t = "cdef", cost = 3
輸出：1
解釋：s 中的任一字符要想變成 t 中對(duì)應(yīng)的字符，其開銷都是 2。因此，最大長(zhǎng)度為 1。

示例 3：

輸入：s = "abcd", t = "acde", cost = 0
輸出：1
解釋：你無(wú)法作出任何改動(dòng)，所以最大長(zhǎng)度為 1。
 

提示：

1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
s 和 t 都只含小寫英文字母。

二、解題思路

滑動(dòng)窗口，先計(jì)算各個(gè)對(duì)應(yīng)位置的字母ASCII碼的差值，然后從左到右累計(jì)開銷，如果大于最大開銷，則窗口左端右移，并減去原始左端的開銷，同時(shí)更新最大長(zhǎng)度。最后再次更新最大長(zhǎng)度即可。

三、代碼

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使字符串相等”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！