在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string. Example 1: Input:s1 = "ab" s2 = "eidbaooo" Output:True Explanation: s2 contains one permutation of s1 ("ba"). Example 2: Input:s1= "ab" s2 = "eidboaoo" Output: False Note:
给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。 换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba"). 示例2: 输入: s1= "ab" s2 = "eidboaoo" 输出: False 注意:
36ms 1 class Solution { 2 func checkInclusion(_ s1: String, _ s2: String) -> Bool { 3 guard s1.count <= s2.count else { 4 return false 5 } 6 7 func allZero(_ counts: [Int]) -> Bool { 8 for i in 0 ..< 26 { 9 if counts[i] != 0 { 10 return false 11 } 12 } 13 return true 14 } 15 16 let chars1 = Array(s1.unicodeScalars) 17 let chars2 = Array(s2.unicodeScalars) 18 let len1 = chars1.count 19 let len2 = chars2.count 20 var counts = [Int](repeatElement(0, count: 26)) 21 22 for i in 0 ..< len1 { 23 counts[Int(chars1[i].value - 97)] += 1 24 counts[Int(chars2[i].value - 97)] -= 1 25 } 26 27 if allZero(counts) { return true } 28 29 for i in len1 ..< len2 { 30 counts[Int(chars2[i].value - 97)] -= 1 31 counts[Int(chars2[i - len1].value - 97)] += 1 32 if allZero(counts) { return true } 33 } 34 35 return false 36 } 37 } 48ms 1 class Solution { 2 func checkInclusion(_ s1: String, _ s2: String) -> Bool { 3 4 var s1Array = Array(s1.characters) 5 var s2Array = Array(s2.characters) 6 7 if s1Array.count > s2Array.count { 8 return false 9 } 10 11 var array1 = Array(repeating:0,count:26) 12 13 var array2 = Array(repeating:0,count:26) 14 15 for i in 0 ..< s1Array.count { 16 let index1 = Int(s1Array[i].unicodeScalars.first!.value) - 97 17 let index2 = Int(s2Array[i].unicodeScalars.first!.value) - 97 18 19 array1[index1] += 1 20 array2[index2] += 1 21 } 22 23 var end = s1Array.count - 1 24 var start = 0 25 while end < s2Array.count{ 26 27 if isMatch(array1,array2){ 28 return true 29 }else{ 30 31 let index = Int(s2Array[start].unicodeScalars.first!.value) - 97 32 array2[index] -= 1 33 start += 1 34 35 end += 1 36 if end < s2Array.count { 37 let index2 = Int(s2Array[end].unicodeScalars.first!.value) - 97 38 array2[index2] += 1 39 } 40 } 41 } 42 43 return false 44 45 } 46 47 func isMatch(_ array1:[Int], _ array2:[Int]) -> Bool{ 48 for i in 0 ..< array1.count { 49 if array1[i] != array2[i]{ 50 return false 51 } 52 } 53 return true 54 } 55 } 52ms 1 class Solution { 2 func checkInclusion(_ s1: String, _ s2: String) -> Bool { 3 var s1 = Array(s1) 4 var s2 = Array(s2) 5 let len1 = s1.count 6 let len2 = s2.count 7 if len1 > len2 { return false } 8 let base = Character("a").asciiValue 9 var count = Array(repeating: 0, count: 26) 10 11 for i in 0..<len1 { 12 count[s1[i].asciiValue - base] += 1 13 count[s2[i].asciiValue - base] -= 1 14 } 15 16 if isAllZero(count) { return true } 17 18 for i in len1..<len2 { 19 count[s2[i].asciiValue - base] -= 1 20 count[s2[i-len1].asciiValue - base] += 1 21 if isAllZero(count) { return true } 22 } 23 return false 24 } 25 26 func isAllZero(_ arr: [Int]) -> Bool { 27 for num in arr { 28 if num != 0 { return false } 29 } 30 return true 31 } 32 } 33 34 extension Character { 35 var asciiValue: Int { 36 get { 37 let s = String(self).unicodeScalars 38 return Int(s[s.startIndex].value) 39 } 40 } 41 } Runtime: 56 ms
Memory Usage: 19.2 MB
1 class Solution { 2 func checkInclusion(_ s1: String, _ s2: String) -> Bool { 3 var arr1:[Character] = Array(s1) 4 var arr2:[Character] = Array(s2) 5 var n1:Int = s1.count 6 var n2:Int = s2.count 7 var cnt:Int = n1 8 var left:Int = 0 9 var m:[Int] = [Int](repeating:0,count:128) 10 for c in arr1 11 { 12 m[c.ascii] += 1 13 } 14 for right in 0..<n2 15 { 16 if m[arr2[right].ascii] > 0 17 { 18 cnt -= 1 19 } 20 m[arr2[right].ascii] -= 1 21 while(cnt == 0) 22 { 23 if right - left + 1 == n1 24 { 25 return true 26 } 27 m[arr2[left].ascii] += 1 28 if m[arr2[left].ascii] > 0 29 { 30 cnt += 1 31 } 32 left += 1 33 } 34 } 35 return false 36 } 37 } 38 39 extension Character 40 { 41 //属性:ASCII整数值(定义小写为整数值) 42 var ascii: Int { 43 get { 44 let s = String(self).unicodeScalars 45 return Int(s[s.startIndex].value) 46 } 47 } 48 } 72ms 1 class Solution { 2 func checkInclusion(_ s1: String, _ s2: String) -> Bool { 3 4 // if s1 permutation is in s2 5 6 let string1 = Array(s1) 7 let string2 = Array(s2) 8 9 let originalCharacterToCount = string1.reduce(into: [:], { $0[$1, default: 0] += 1 }) 10 11 var currentCharacterToCount: [Character:Int] = [:] 12 var startIndex = 0 13 14 for endIndex in 0..<string2.count { 15 16 let character = string2[endIndex] 17 18 guard let originalCount = originalCharacterToCount[character] else { 19 // if this character doesn't exist, then we have to start searching for a new one 20 currentCharacterToCount = [:] 21 startIndex = endIndex+1 22 continue 23 } 24 25 currentCharacterToCount[character, default: 0] += 1 26 27 while let currentCount = currentCharacterToCount[character], currentCount > originalCount { 28 // we can't have TOO many characters - it must match the substring 29 // 30 // the guard statment already ensures that we have the RIGHT characters 31 // 32 // now we have to worry about the COUNT of the characters 33 let startCharacter = string2[startIndex] 34 currentCharacterToCount[startCharacter, default: 0] -= 1 35 startIndex += 1 36 } 37 38 if (endIndex - startIndex + 1) == string1.count { 39 return true 40 } 41 } 42 43 return false 44 } 45 } 76ms 1 class Solution { 2 3 func checkInclusion(_ s1: String, _ s2: String) -> Bool { 4 5 let string1Count = s1.count 6 let string2 = Array(s2) 7 8 let originalCharacterToCount = s1.reduce( 9 into: [:], 10 { $0[$1, default: 0] += 1 }) 11 12 var startIndex = 0 13 var currentCharacterToCount: [Character:Int] = [:] 14 15 for endIndex in 0..<string2.count { 16 let character = string2[endIndex] 17 18 guard let originalCount = originalCharacterToCount[character] else { 19 // reset 20 startIndex = endIndex+1 21 currentCharacterToCount = [:] 22 continue 23 } 24 25 // count 26 currentCharacterToCount[character, default: 0] += 1 27 28 // adjust startIndex in case we over-counted 29 while let currentCount = currentCharacterToCount[character], currentCount > originalCount { 30 let startCharacter = string2[startIndex] 31 startIndex += 1 32 currentCharacterToCount[startCharacter, default: 1] -= 1 33 } 34 35 // we don't need character count, we can just use startIndex - endIndex 36 if (endIndex-startIndex+1) == string1Count { 37 return true 38 } 39 } 40 41 return false 42 } 43 } 80ms 1 class Solution { 2 func checkInclusion(_ s1: String, _ s2: String) -> Bool { 3 if s1.characters.count > s2.characters.count { 4 return false 5 } 6 7 let chars1 = Array(s1.characters) 8 let chars2 = Array(s2.characters) 9 let len1 = chars1.count 10 let len2 = chars2.count 11 var counts = [Int](repeatElement(0, count: 256)) 12 13 for i in 0..<len1 { 14 counts[Int((chars1[i].unicodeScalars.first?.value)!)] += 1 15 counts[Int((chars2[i].unicodeScalars.first?.value)!)] -= 1 16 } 17 if allZero(counts) { 18 return true 19 } 20 for i in len1..<len2 { 21 counts[Int((chars2[i].unicodeScalars.first?.value)!)] -= 1 22 counts[Int((chars2[i - len1].unicodeScalars.first?.value)!)] += 1 23 if allZero(counts) { 24 return true 25 } 26 } 27 28 return false 29 } 30 31 private func allZero(_ counts: [Int]) -> Bool { 32 for i in 0..<256 { 33 if counts[i] != 0 { 34 return false 35 } 36 } 37 return true 38 } 39 } 84ms 1 class Solution { 2 func checkInclusion(_ s1: String, _ s2: String) -> Bool { 3 let s1Lower = LowerCaseString(s1) 4 let s2Lower = LowerCaseString(s2) 5 6 let s1Counts = LowerCaseCounter(from: s1Lower).counts 7 guard let s2Counter = LowerCaseCounter(from: s2Lower, 8 using: s1Lower.data.count) else { 9 return false 10 } 11 12 if s1Counts == s2Counter.counts { return true } 13 14 while let s2Counts = s2Counter.step() { 15 if s1Counts == s2Counts { return true } 16 } 17 18 return false 19 } 20 } 21 22 func unicode(_ c: Character) -> Int { 23 return Int(c.unicodeScalars.first!.value) 24 } 25 26 enum LowerCase: Int { 27 case a = 97 28 case b 29 case c 30 case d 31 case e 32 case f 33 case g 34 case h 35 case i 36 case j 37 case k 38 case l 39 case m 40 case n 41 case o 42 case p 43 case q 44 case r 45 case s 46 case t 47 case u 48 case v 49 case w 50 case x 51 case y 52 case z 53 } 54 55 struct LowerCaseString { 56 private(set) var data: [LowerCase] 57 58 init(_ s: String) { 59 data = [] 60 data.reserveCapacity(s.count) 61 for c in s { 62 let u = unicode(c) 63 guard let e = LowerCase(rawValue: u) else { continue } 64 data.append(e) 65 } 66 } 67 } 68 69 70 class LowerCaseCounter { 71 private static var len = 1 + LowerCase.z.rawValue - LowerCase.a.rawValue 72 private(set) var counts: [Int] = Array(repeating: 0, count: Int(len)) 73 74 private var start: IndexingIterator<[LowerCase]> 75 private var end: IndexingIterator<[LowerCase]> 76 77 init(from s: LowerCaseString) { 78 start = s.data.makeIterator() 79 end = s.data.makeIterator() 80 while let on = end.next() { 81 let i = on.rawValue - LowerCase.a.rawValue 82 counts[i] = counts[i] + 1 83 } 84 } 85 86 init?(from s: LowerCaseString, using n: Int) { 87 start = s.data.makeIterator() 88 end = s.data.makeIterator() 89 for _ in 0..<n { 90 guard let on = end.next() else { return nil } 91 let i = on.rawValue - LowerCase.a.rawValue 92 counts[i] = counts[i] + 1 93 } 94 } 95 96 func step() -> [Int]? { 97 guard let on = end.next() else { return nil } 98 guard let off = start.next() else { return nil } 99 100 let i = on.rawValue - LowerCase.a.rawValue 101 let j = off.rawValue - LowerCase.a.rawValue 102 103 counts[i] = counts[i] + 1 104 counts[j] = max(counts[j] - 1, 0) 105 106 |
请发表评论