[Swift]LeetCode567. 字符串的排列 | Permutation in String

it2022-05-06 10

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

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:

The input strings only contain lower case letters.The length of both given strings is in range [1, 10,000].

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba").

示例2:

输入: s1= "ab" s2 = "eidboaoo" 输出: False

注意：

输入的字符串只包含小写字母两个字符串的长度都在 [1, 10,000] 之间

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 return counts 107 } 108 }

92ms

1 class Solution { 2 func checkInclusion(_ s1: String, _ s2: String) -> Bool { 3 4 let a1 = Array(s1).map { String($0) } 5 let len = a1.count 6 let a2 = Array(s2).map { String($0) } 7 if a2.count < len { return false } 8 var hashA = [String:Int]() 9 for s in a1 { 10 if let old = hashA[s] { 11 hashA[s] = old+1 12 } else { 13 hashA[s] = 1 14 } 15 } 16 17 18 var hashB = [String:Int]() 19 20 var i = 0 21 while i<len{ 22 let s = a2[i] 23 if let old = hashB[s] { 24 hashB[s] = old+1 25 } else { 26 hashB[s] = 1 27 } 28 i+=1 29 } 30 var runnerHashB = hashB 31 32 if runnerHashB == hashA { 33 return true 34 } 35 var j = 0 36 37 while j < (a2.count - len) { 38 39 if let old = runnerHashB[a2[j]] { 40 if old == 1 { 41 runnerHashB[a2[j]] = nil 42 } else { 43 runnerHashB[a2[j]] = old - 1 44 } 45 46 } 47 48 if let old1 = runnerHashB[a2[j+len]] { 49 runnerHashB[a2[j+len]] = old1 + 1 50 } else { 51 runnerHashB[a2[j+len]] = 1 52 } 53 if runnerHashB == hashA { 54 return true 55 } 56 j+=1 57 } 58 return false 59 } 60 }

100ms

1 class Solution { 2 func checkInclusion(_ s1: String, _ s2: String) -> Bool { 3 4 if s1.count > s2.count { return false } 5 6 var dict1 = [Character: Int]() 7 var dict2 = dict1 8 s1.forEach { 9 dict1[$0] = (dict1[$0] ?? 0) + 1 10 } 11 12 13 let s2 = Array(s2) 14 let n = s1.count 15 for i in 0..<s2.count { 16 dict2[s2[i]] = (dict2[s2[i]] ?? 0) + 1 17 if i >= n { 18 let count = dict2[s2[i - n]]! 19 dict2[s2[i - n]] = count == 1 ? nil : count - 1 20 } 21 if dict2 == dict1 { 22 return true 23 } 24 } 25 26 return false 27 } 28 }

104ms

1 class Solution { 2 func checkInclusion(_ s1: String, _ s2: String) -> Bool { 3 guard !s1.isEmpty && !s2.isEmpty && s2.count >= s1.count else { 4 return false 5 } 6 7 var map: [Character: Int] = [:] 8 for char in s1 { 9 if let count = map[char] { 10 map[char] = count + 1 11 } else { 12 map[char] = 1 13 } 14 } 15 16 let chars = Array(s2) 17 var temp = map 18 var left = 0 19 for (index, char) in chars.enumerated() { 20 if let count = temp[char] { 21 if count > 0 { 22 let newCount = count - 1 23 temp[char] = newCount 24 if newCount == 0 { 25 let empty = temp.contains { $0.value > 0 } 26 if !empty { 27 return true 28 } 29 } 30 } else { 31 if chars[left] == char { 32 left += 1 33 } else { 34 var index2 = left 35 while true { 36 let char2 = chars[index2] 37 if char2 != char { 38 temp[char2] = temp[char2]! + 1 39 } else { 40 left = index2 + 1 41 break 42 } 43 index2 += 1 44 } 45 } 46 } 47 } else { 48 temp = map 49 left = index + 1 50 } 51 } 52 53 return false 54 } 55 }

148ms

1 class Solution { 2 func checkInclusion(_ s1: String, _ s2: String) -> Bool { 3 4 if s1 == "" { 5 return true 6 } 7 8 var hash = [Character: Int]() 9 10 for ch in s1 { 11 hash[ch] = hash[ch, default: 0] - 1 12 } 13 14 var count = hash.count 15 16 var frt = 0 17 var chArr = Array(s2) 18 for (i, ch) in s2.enumerated() { 19 hash[ch] = hash[ch, default: 0] + 1 20 if hash[ch] == 0 { 21 hash[ch] = nil 22 count -= 1 23 } 24 25 if count == 0 { 26 while frt < i { 27 var f = chArr[frt] 28 if let val = hash[f] { 29 hash[f] = hash[f]! - 1 30 if hash[f] == 0 { 31 hash[f] = nil 32 } 33 frt += 1 34 } else { 35 break 36 } 37 } 38 } 39 40 if hash.count == 0 { 41 return true 42 } 43 } 44 return false 45 } 46 }

232ms

1 class Solution { 2 func checkInclusion(_ s1: String, _ s2: String) -> Bool { 3 let len1 = s1.count 4 let len2 = s2.count 5 6 guard len1 <= len2 else { return false } 7 8 var countDict = [Character: Int]() 9 10 var s1 = Array(s1) 11 var s2 = Array(s2) 12 13 for i in 0..<len1 { 14 if let value = countDict[s1[i]] { 15 countDict[s1[i]] = value + 1 16 } else { 17 countDict[s1[i]] = 1 18 } 19 20 if let value = countDict[s2[i]] { 21 countDict[s2[i]] = value - 1 22 } else { 23 countDict[s2[i]] = -1 24 } 25 } 26 27 if allZeroes(countDict.map { $0.value }) { return true } 28 29 for i in len1..<len2 { 30 if let value = countDict[s2[i]] { 31 countDict[s2[i]] = value - 1 32 } else { 33 countDict[s2[i]] = -1 34 } 35 36 if let value = countDict[s2[i - len1]] { 37 countDict[s2[i - len1]] = value + 1 38 } else { 39 countDict[s2[i - len1]] = 1 40 } 41 42 if allZeroes(countDict.map { $0.value }) { return true } 43 } 44 45 return false 46 } 47 48 func allZeroes(_ nums: [Int]) -> Bool { 49 for num in nums { 50 if num != 0 { 51 return false 52 } 53 } 54 55 return true 56 } 57 }

转载于:https://www.cnblogs.com/strengthen/p/10420668.html

专利

最新回复(0)