[Swift]LeetCode76.最小覆盖子串|MinimumWindowSubstring

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

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

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

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

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

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

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

40ms

 1 class Solution {
 2 //initialize two pointers- left and right and initialize both to the first element of string s.
 3 //In any sliding window problem, we have two pointers. One right pointer whose job is to expand the current
 4 //window and the left pointer whose hob is to contract the given window. At any point, only one of those pointers
 5 //move and the other stay fixed.
 6 
 7 func minWindow(_ s: String, _ t: String) -> String {
 8     //convert the strings to character array
 9     //the map is necessary to convert uint8 to Int
10     let schars = Array(s.utf8).map {Int($0)}
11     let tchars = Array(t.utf8).map {Int($0)}
12     
13     
14     //create hashmap
15     var hash = Array(repeating: 0, count: 128)
16     
17     for tchar in tchars {
18         hash[tchar] += 1
19     }
20     
21     var count = tchars.count
22     var start = 0
23     var left = 0
24     var right = 0
25     var length = Int.max
26     
27     //We use the right pointer to expand the window until we get a desirable window i.e. a window that contains all of the characters of
28     // t
29     while right < schars.count {
30         //if this character from schars is present in hash (i.e. in tchars), decrement count and also the count for that char in the hash by 1.
31         if hash[schars[right]] > 0 {
32             count -= 1
33         }
34         hash[schars[right]] -= 1
35         right += 1
36         
37         while count == 0 {
38             if right - left < length {
39                 //keep updating the length value
40                 length = right - left
41                 start = left
42             }
43             //Once we have a window with all the characters, we can move the left pointer ahead one by one. If the window is still a desirable one we keep //updating the minimum window size.
44             if hash[schars[left]] == 0 {
45                 count += 1
46             }
47             hash[schars[left]] += 1
48             left += 1
49         }
50     }
51     
52     //not present
53     if length > schars.count {
54         return ""
55     }
56     
57     let index1 = s.index(s.startIndex, offsetBy: start)
58     let index2 = s.index(s.startIndex, offsetBy: start + length)
59     
60     return String(s[index1..<index2])
61   }
62 }

44ms

 1 class Solution {
 2     func minWindow(_ s: String, _ t: String) -> String {
 3     
 4         let tt = Array(t.utf16).map { Int($0) }
 5         let ss = Array(s.utf16).map { Int($0) }
 6         // create hashmap
 7         var hash = [Int](repeating: 0, count: 128)
 8         for n in tt {
 9             hash[n] += 1
10         }
11 
12         var count = tt.count, start = 0, l = 0, r = 0, length = Int.max
13 
14         while r < ss.count {
15             if hash[ss[r]] > 0 {
16                 count -= 1
17             }
18             hash[ss[r]] -= 1
19             r += 1
20             while count == 0 {
21                 if r - l < length {
22                     length = r - l
23                     start = l
24                 }
25                 if hash[ss[l]] == 0 {
26                     count += 1
27                 }
28                 hash[ss[l]] += 1
29                 l += 1
30             }
31         }
32 
33         if length > ss.count {
34             return ""
35         }
36 
37         let index1 = s.index(s.startIndex, offsetBy: start)
38         let index2 = s.index(s.startIndex, offsetBy: start + length)
39         return s.substring(with: index1..<index2)
40     }
41 }

48ms

 1 class Solution {
 2     func minWindow(_ s: String, _ t: String) -> String {
 3         let ss = Array(s.utf8).map(Int.init)
 4         let tt = Array(t.utf8).map(Int.init)
 5         var counts = [Int](repeating: 0, count: 256)
 6         for char in tt {
 7             counts[char] += 1
 8         }
 9         var left = 0
10         var size = t.count
11         var res = (-1, -1)
12         var minL = Int.max
13         for right in 0..<s.count {
14             counts[ss[right]] -= 1
15             if counts[ss[right]] >= 0 {
16                 size -= 1
17             }
18             
19             if size == 0 {
20                 inner: while left < right {
21                     counts[ss[left]] += 1
22                     if counts[ss[left]] > 0 {
23                         size += 1
24                         break inner
25                     }
26                     left += 1
27                 }
28                 if right - left + 1 < minL {
29                     minL = right - left + 1
30                     res = (left, right)
31                 }
32                 left += 1
33             }
34         }
35         if res == (-1, -1) { return "" }
36         let arr = ss[res.0...res.1]
37         return String(arr.map { Character(UnicodeScalar($0)!) } )
38     }
39 }

Runtime: 52 ms

Memory Usage: 20.3 MB

 1 class Solution {
 2     func minWindow(_ s: String, _ t: String) -> String {
 3         var counter:Int = 0
 4         var minlen:Int = Int.max
 5         var begin:Int = 0
 6         var end:Int = 0
 7         var head:Int = 0
 8         var m:[Int] = [Int](repeating:0,count:128)
 9         counter = t.count
10         var arrT:[Int] = Array(t).map{$0.ascii}
11         for c in arrT
12         {
13             m[c]++
14         }
15         var arrS:[Int] = Array(s).map{$0.ascii}
16         while(end < arrS.count)
17         {
18             if m[arrS[end++]]-- > 0
19             {
20                 counter--
21             }
22             while(counter==0)
23             {
24                 if minlen > end - begin
25                 {
26                     head = begin
27                     minlen = end - (head)
28                 }
29                 if m[arrS[begin++]]++ == 0
30                 {
31                     counter++
32                 }
33             }            
34         }
35         let str:String = (minlen == Int.max) ? "" :s.subString(head,minlen)
36         return str
37         
38     }
39 }
40 
41 /*扩展Int类，实现自增++、自减--运算符*/
42 extension Int{
43     //后缀++:先执行表达式后再自增
44     static postfix func ++(num:inout Int) -> Int {
45         //输入输出参数num
46         let temp = num
47         //num加1
48         num += 1
49         //返回加1前的数值
50         return temp
51     }
52     //后缀--:先执行表达式后再自减
53     static postfix func --(num:inout Int) -> Int {
54         //输入输出参数num
55         let temp = num
56         //num减1
57         num -= 1
58          //返回减1前的数值
59         return temp
60     }
61 }
62 
63 
64 //Character扩展方法  
65 extension Character  
66 {  
67   //属性：ASCII整数值(定义小写为整数值)
68    var ascii: Int {
69         get {
70             let s = String(self).unicodeScalars
71             return Int(s[s.startIndex].value)
72         }
73     }
74 }
75 
76 extension String {
77     
78     // 截取字符串：指定索引和字符数
79     // - begin: 开始截取处索引
80     // - count: 截取的字符数量
81     func subString(_ begin:Int,_ count:Int) -> String {
82         let start = self.index(self.startIndex, offsetBy: max(0, begin))
83         let end = self.index(self.startIndex, offsetBy:  min(self.count, begin + count))
84         return String(self[start..<end]) 
85     }
86 }

52ms

 1 class Solution {
 2     func minWindow(_ s: String, _ t: String) -> String {
 3         var chs = Array(s)
 4         let s = s.map { letterIndex($0) }
 5         let t = t.map { letterIndex($0) }
 6         var map = [Int](repeating:0, count:256)
 7         for ch in t {
 8             map[ch] += 1
 9         }
10         var minLen = Int.max, count = t.count
11         var j = 0, startIndex = 0
12         for i in 0..<s.count {
13             while j < s.count && count > 0 {
14                 if map[s[j]] > 0 {
15                     count -= 1
16                 }
17                 map[s[j]] -= 1
18                 j += 1
19             }
20             if count == 0 && j - i < minLen{
21                 minLen = j - i
22                 startIndex = i
23             }
24             if map[s[i]] >= 0 {
25                 count += 1 
26             }
27             map[s[i]] += 1
28         }
29         return minLen == Int.max ? "" : String(chs[startIndex..<(startIndex+minLen)])
30     }
31     
32     func letterIndex(_ letter: Character) -> Int {
33         return Int(letter.unicodeScalars.first!.value)
34     }
35 }

72ms

 1 class Solution {
 2     func minWindow(_ s: String, _ t: String) -> String {
 3         var map = [Character : Int]()   //t's char and count
 4         var diff = t.count 
 5         var left = 0
 6         var right = 0
 7         // var res = ""
 8         var len = Int.max
 9         var start = 0
10         let sArr = Array(s)
11         for char in t {
12             map[char, default: 0 ] += 1   // count
13         }
14 
15         while right < sArr.count {
16             let char = sArr[right]
17             
18             if let count = map[char] {  //t has this char
19                 if count > 0 {          //this is useful to diff
20                     diff -= 1
21                 }
22                 map[char] = count - 1
23             }
24             if diff == 0 {  // found an ans
25                 while left <= right{
26                     if let count = map[sArr[left]] {
27                         if count == 0 {
28                             if right - left + 1 < len{
29                                 len = right - left + 1 
30                                 start = left
31                             }
32                             map[sArr[left]] = count + 1
33                             left += 1
34                             diff += 1
35                             break
36                         }
37                         map[sArr[left]] = count + 1
38                     }
39                     left += 1
40                 } 
41             }
42     
43             right += 1
44         }
45         if len == Int.max { return "" }
46         //              print(start)
47         //              print(len)
48         return String(sArr[start ..< start + len])
49     }
50 }

76ms

 1 class Solution {
 2     func minWindow(_ s: String, _ t: String) -> String {
 3         guard s.count>=t.count else {return ""}
 4         
 5         var dic = [String.Element:Int]()
 6         let sChars = Array(s)
 7         let tChars = Array(t)
 8         
 9         for char in tChars {
10             if let val = dic[char] {
11                 dic[char] = val+1
12             } else {
13                 dic[char] = 1
14             }
15         }
16         
17         var start = 0
18         var minStart = 0, minLength = Int.max
19         var numOfTargets = t.count
20         
21         for end in 0..<sChars.count {
22 
23             if let curOcurrance = dic[sChars[end]] {
24                 if curOcurrance > 0 {
25                     numOfTargets -= 1
26                 }
27                 dic[sChars[end]] = curOcurrance-1
28             }
29 
30             while numOfTargets == 0 {
31                 if minLength > end-start+1 {
32                     minLength = end-start+1
33                     minStart = start
34                 }
35                 
36                 if let curOccurance = dic[sChars[start]] {
37                     if curOccurance == 0 {
38                         numOfTargets += 1
39                     }
40                     dic[sChars[start]] = curOccurance+1
41                 }
42                 start+=1
43             }
44         }
45 
46         return minLength == Int.max ? "" : String(sChars[minStart..<minStart+minLength])
47     }
48 }

84ms

 1 class Solution {
 2     func minWindow(_ s: String, _ t: String) -> String {
 3         var len = Int.max
 4         var count = t.count
 5         var result = ""
 6         
 7         var dict: [Character: Int] = [:]
 8         for c in t {
 9             dict[c, default: 0] += 1
10         }
11         
12         var i = 0, start = 0
13         var startIndex = s.startIndex, iIndex = s.startIndex
14         
15         while iIndex < s.endIndex {
16             let c = s[iIndex]
17             
18             if let cnt = dict[c] {
19                 dict[c] = cnt - 1
20                 
21                 if cnt >= 1 {
22                     count -= 1    
23                 }
24             }
25             
26             while count == 0 && start <= i {
27                 if i - start + 1 < len {
28                     len = i - start + 1
29                     result = String(s[startIndex...iIndex])
30                 }
31                 
32                 let startChar = s[startIndex]
33                 if let cnt = dict[startChar] {
34                     dict[startChar] = cnt + 1
35                     
36                     if cnt >= 0 {
37                         count += 1    
38                     }
39                 }
40                 start += 1
41                 startIndex = s.index(after: startIndex)
42             }
43             
44             iIndex = 
                       
                    
                     
                      



鲜花




握手




雷人




路过




鸡蛋