[Swift]LeetCode1208.尽可能使字符串相等|GetEqualSubstringsWithinBudget

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（let_us_code）
➤博主域名：https://www.zengqiang.org
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

You are given two strings s and t of the same length. You want to change s to t. Changing the i-th character of s to i-th character of t costs |s[i] - t[i]| that is, the absolute difference between the ASCII values of the characters.

You are also given an integer maxCost.

Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of twith a cost less than or equal to maxCost.

If there is no substring from s that can be changed to its corresponding substring from t, return 0.

Example 1:

Input: s = "abcd", t = "bcdf", cost = 3
Output: 3
Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.

Example 2:

Input: s = "abcd", t = "cdef", cost = 3
Output: 1
Explanation: Each charactor in s costs 2 to change to charactor in t, so the maximum length is 1.

Example 3:

Input: s = "abcd", t = "acde", cost = 0
Output: 1
Explanation: You can't make any change, so the maximum length is 1.

Constraints:

1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
s and t only contain lower case English letters.

给你两个长度相同的字符串，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 都只含小写英文字母。

Runtime: 64 ms

Memory Usage: 24 MB

 1 class Solution {
 2     func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
 3         let s:[Int] = Array(s).map{$0.ascii}
 4         let t:[Int] = Array(t).map{$0.ascii}
 5         var ans:Int = 0
 6         var l:Int = 0
 7         var r:Int = -1
 8         var curCost:Int = 0
 9         for i in 0..<s.count
10         {
11             r += 1
12             curCost += abs(s[r] - t[r])
13             while(curCost > maxCost && l <= r)
14             {
15                 curCost -= abs(s[l] - t[l])
16                 l += 1
17             }
18             ans = max(ans, r - l + 1)
19         }
20         return ans
21     }
22 }
23 
24 
25 //Character扩展 
26 extension Character  
27 {  
28   //Character转ASCII整数值(定义小写为整数值)
29    var ascii: Int {
30        get {
31            return Int(self.unicodeScalars.first?.value ?? 0)
32        }       
33     }
34 }

24ms

 1 class Solution {
 2     func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
 3         let s = Array(s.utf8)
 4         let t = Array(t.utf8)
 5         var res = [Int](repeating: 0, count: s.count)
 6         for i in 0..<s.count {
 7             res[i] = abs(Int(s[i]) - Int(t[i]))
 8         }
 9         //print(res)
10         var left = 0
11         var right = 0
12         var cost = 0
13         var ans = 0
14         while right < res.count {
15             cost += res[right]
16             ans = max(ans, right - left)
17             while cost > maxCost && left <= right {
18                 cost -= res[left]
19                 left += 1
20             }
21             right += 1
22         }
23         ans = max(ans, right - left)
24         return ans
25     }
26 }

36ms

 1 class Solution {
 2     func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
 3         guard s.count == t.count else {
 4             return 0
 5         }
 6         
 7         let arrayS = Array(s)
 8         let arrayT = Array(t)
 9         
10         var diffs = [0]
11         
12         for i in 0..<arrayS.count {
13             guard let v1 = arrayS[i].asciiValue, let v2 = arrayT[i].asciiValue else {
14                 return 0
15             }
16             
17             let diff = abs(Int(v1) - Int(v2))
18             diffs.append(diff)
19         }
20         var head = 0
21         var currentCost = 0
22         var length = 0
23         var maxLength = 0
24         
25         // print(diffs)
26         
27         for tail in 1..<diffs.count {
28             currentCost += diffs[tail]
29             length += 1
30             
31             if currentCost <= maxCost, currentCost >= 0 {
32                 // print("head:\(head)...tail:\(tail)....\(currentCost)")
33                 maxLength = max(maxLength, length)
34             } else {
35                 for h in head+1..<tail {
36                     currentCost -= diffs[h]
37                     length -= 1
38                     head = h
39                     if currentCost <= maxCost, currentCost >= 0 {
40                         // print("head:\(head)...tail:\(tail)....\(currentCost)")
41                         maxLength = max(maxLength, length)
42                         break
43                     }
44                 }
45             }
46         }
47         return maxLength
48     }
49 }

40ms

 1 class Solution {
 2     func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
 3         var diff = [Int](repeating: 0, count: t.count)
 4         var sArr: [Character] = Array(s)
 5         var tArr: [Character] = Array(t)
 6         
 7         for i in 0..<s.count {
 8             diff[i] = absoluteDifference(sArr[i], tArr[i])
 9         }
10 
11         var result = 0
12         var startIndex = 0
13         var endIndex = 0
14         var sum = 0
15         
16         while endIndex < diff.count {
17             if sum <= maxCost {
18                 sum += diff[endIndex]
19                 if sum <= maxCost {
20                     result = max((endIndex - startIndex) + 1, result)
21                 }
22                 endIndex += 1
23             } else {
24                 if startIndex < endIndex {
25                     sum -= diff[startIndex]
26                     startIndex += 1
27                 } else {
28                     startIndex += 1
29                     endIndex += 1
30                 }
31             }
32 
33         }
34         
35         return result
36     }
37     
38     private func absoluteDifference(_ charOne: Character, _ charTwo: Character) -> Int {
39         return abs(Int(charOne.asciiValue!) - Int(charTwo.asciiValue!))
40     }
41 }

44ms

 1 class Solution {
 2     func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
 3         
 4         var sa = s.map { Int($0.asciiValue!) }
 5         var ta = t.map { Int($0.asciiValue!) }
 6         
 7         var i = 0
 8         var j = 0
 9         var k = maxCost
10         
11         while j < sa.count {
12             
13             let cost = abs(sa[j] - ta[j])
14             k -= cost
15             
16             if k < 0 {
17                 k += abs(sa[i] - ta[i])
18                 i += 1
19             }
20             
21             j += 1
22         }
23         
24         return j - i
25     }
26 }

52ms

 1 class Solution {
 2     func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
 3         guard s.count == t.count else {
 4             return 0
 5         }
 6         
 7         let arrayS = Array(s)
 8         let arrayT = Array(t)
 9         
10         var diffs = [0]
11         
12         for i in 0..<arrayS.count {
13             guard let v1 = arrayS[i].asciiValue, let v2 = arrayT[i].asciiValue else {
14                 return 0
15             }
16             
17             let diff = abs(Int(v1) - Int(v2))
18             diffs.append(diff)
19         }
20         
21         var head = 0
22         var currentCost = 0
23         var length = 0
24         var maxLength = 0
25         
26         for tail in 1..<diffs.count {
27             currentCost += diffs[tail]
28             length += 1
29             
30             if currentCost <= maxCost, currentCost >= 0 {
31                 maxLength = max(maxLength, length)
32             } else {
33                 for h in head+1..<tail {
34                     currentCost -= diffs[h]
35                     length -= 1
36                     head = h
37                     if currentCost <= maxCost, currentCost >= 0 {
38                         maxLength = max(maxLength, length)
39                         break
40                     }
41                 }
42             }
43             
44         }
45         
46         return maxLength
47     }
48 }

56ms

 1 class Solution {
 2     func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
 3         let s = s.map({Int(Character(String($0)).asciiValue!)})
 4         let t = t.map({Int(Character(String($0)).asciiValue!)})
 5         var diff: [Int] = []
 6         for i in 0..<s.count {
 7             diff.append(abs(s[i] - t[i]))
 8         }
 9         
10         var l = 0
11         var r = 0
12         var count = diff[0]
13         var maxLength = diff[0] == 0 ? 1 : 0
14         
15         while l < diff.count - maxLength {
16             r += 1
17             count += diff[r]
18             if count > maxCost {
19                 count -= diff[r]
20                 count -= diff[l]
21                 l += 1
22                 r -= 1
23             } else {
24                 if r - l + 1 > maxLength {
25                     maxLength = r - l + 1
26                 }
27             }
28         }
29         //print(diff)
30         return maxLength
31     }
32 }

108ms

 1 class Solution {
 2     func asciiValue(_ char: Character) -> Int {
 3         let s = String(char).unicodeScalars
 4         return Int(s[s.startIndex].value)
 5     }
 6     
 7     func equalSubstring(_ s: String, _ t: String, _ maxCost: Int) -> Int {
 8         
 9         let codesS = s.map(asciiValue)
10         let codesT = t.map(asciiValue)
11         
12         var costs = [Int]()
13 
14         for i in 0..<codesS.count {
15             costs.append(abs(codesS[i] - codesT[i]))
16         }
17         
18         print(costs)
19         
20         var maxLen = 0
21         var currentLen = 0
22         
23         var budget = maxCost
24         for (index, cost) in costs.enumerated() {
25             
26             // try to increase substring
27             budget -= cost
28             
29             // if within the budget increment current length
30             if budget >= 0 {
31                 currentLen += 1
32             } else {
33                 // otherwise check if we
34                 if currentLen > maxLen {
35                     maxLen = currentLen
36                 }
37                 
38                 // update current len and budget
39                 while budget < 0 && currentLen > 0 {
40                     budget += costs[index - currentLen]
41                     currentLen -= 1
42                 }
43                 
44                 if budget >= 0 {
45                     currentLen += 1
46                     maxLen = max(maxLen, currentLen)
47                 }
48                 
49                 if currentLen == 0 {
50                     budget += costs[index]
51                 }
52             }
53         }
54         
55         return max(maxLen, currentLen)
56     }
57 }