[Swift]LeetCode438.找到字符串中所有字母异位词|FindAllAnagramsinaString ...

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

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

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

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

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

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

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and pwill not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。

示例 1:

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2:

输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

56ms

 1 class Solution {
 2     func findAnagrams(_ s: String, _ p: String) -> [Int] {
 3         let sCount = s.utf8.count
 4         let pCount = p.utf8.count
 5         guard sCount >= pCount else {
 6             return []
 7         }
 8         var a = 97
 9         var map = [Int](repeating: 0, count: 26)
10         p.utf8.forEach({
11             map[Int($0) - a] += 1
12         })
13         var sArray = Array(s.utf8)
14         var left = 0
15         var right = 0
16         var count = 0 
17         var res = [Int]()
18         
19         while right < sCount {
20             let rightIndex = Int(sArray[right]) - a
21             if map[rightIndex] > 0 {
22                 map[rightIndex] -= 1
23                 right += 1
24                 count += 1
25             } else {
26                 let leftIndex = Int(sArray[left]) - a
27                 map[leftIndex] += 1
28                 left += 1
29                 count -= 1
30             }
31             if count == pCount {
32                 res.append(left)
33             }
34         }
35         return res
36     }
37 }

80ms

 1 class Solution {
 2     func findAnagrams(_ s: String, _ p: String) -> [Int] {
 3         let s = s.map { letterIndex($0) }
 4         let p = p.map { letterIndex($0) }
 5         
 6         var ref = Array(repeating: 0, count: 26)
 7         for char in p {
 8             ref[char] += 1
 9         }
10         
11         var result = [Int]()
12         var map = ref.map { _ in 0 }
13         for i in 0..<s.count {
14             map[s[i]] += 1
15             if i - p.count >= 0 {
16                 map[s[i-p.count]] -= 1
17             }
18 
19             if map == ref {
20                 result.append(i - p.count + 1)
21             }
22         }
23         
24         return result
25     }
26     
27     func letterIndex(_ letter: Character) -> Int {
28         return Int(letter.unicodeScalars.first!.value) - Int(Unicode.Scalar("a").value)
29     }
30 }

84ms

 1 class Solution {
 2     func findAnagrams(_ s: String, _ p: String) -> [Int] {
 3         if s.isEmpty {
 4             return []
 5         }
 6         var hash = Array(repeating: 0, count: 256)
 7         for letter in p {
 8             hash[letter.ascii] += 1
 9         }
10         let s = [Character](s), p = [Character](p)
11         var left = 0, right = 0, count = p.count
12         var result = [Int]()
13         
14         while right < s.count {
15             let index = s[right].ascii
16             if hash[index] >= 1 {
17                 count -= 1
18             }
19             hash[index] -= 1
20             right += 1
21             
22             if count == 0 {
23                 result.append(left)
24             }
25             
26             if right - left == p.count {
27                 let leftIndex = s[left].ascii
28                 if hash[leftIndex] >= 0 {
29                     count += 1
30                 }
31                 hash[leftIndex] += 1
32                 left += 1
33             }
34         }
35         return result
36     }
37 }
38 
39 fileprivate extension Character {
40     var ascii: Int {
41         let utf8 = String(self).utf8
42         return Int(utf8[utf8.startIndex])
43     }
44 }

100ms

 1 class Solution {
 2     func findAnagrams(_ s: String, _ p: String) -> [Int] {
 3         if s.count < p.count {
 4             return []
 5         }
 6 
 7         var s = Array(s)
 8         var i = 0, j = p.count - 1
 9 
10         var pOcc = Array(repeating: 0, count: 26)
11         var sOcc = Array(repeating: 0, count: 26)
12 
13         for char in p {
14             pOcc[char.asciiValue - 97] += 1
15         }
16 
17         for char in s.prefix(p.count) {
18             sOcc[char.asciiValue - 97] += 1
19         }
20 
21         var result = [Int]()
22         while true {
23             if isValidAnagram(pOcc, sOcc) {
24                 result.append(i)
25             }
26 
27             i += 1
28             j += 1
29             if j >= s.count { break }
30 
31             sOcc[s[i - 1].asciiValue - 97] -= 1
32             sOcc[s[j].asciiValue - 97] += 1
33         }
34 
35         return result
36     }
37 
38     func isValidAnagram(_ s: [Int], _ p: [Int]) -> Bool {
39         return s == p
40     }
41 }
42 
43 extension Character {
44     var asciiValue: Int {
45         get {
46             let s = String(self).unicodeScalars
47             return Int(s[s.startIndex].value)
48         }
49     }
50 }

128ms

 1 class Solution {
 2     func findAnagrams(_ s: String, _ p: String) -> [Int] {
 3         guard s.count > 0, s.count >= p.count else {
 4             return []
 5         }
 6         let sarr:[Character] = Array(s)
 7         let parr:[Character] = Array(p)
 8         var count = parr.count
 9         var result = Array<Int>()
10         var map = Dictionary<Character, Int>()
11         
12         for p in parr {
13             if map[p] == nil {
14                 map[p] = 0
15             }
16             map[p]! += 1
17         }
18         
19         var left = 0
20         var right = 0
21         
22         while right < sarr.count {
23             if map[sarr[right]] == nil {
24                 map[sarr[right]] = 0
25             }
26             
27             if map[sarr[right]]! > 0 {
28                 count -= 1
29             }
30             map[sarr[right]]! -= 1
31             right += 1
32             
33             if count == 0 {
34                 result.append(left)
35             }
36             
37             if right - left == parr.count {
38                 if map[sarr[left]] == nil {
39                     map[sarr[left]] = 0
40                 }
41                 if map[sarr[left]]! >= 0 {
42                     count += 1
43                 }
44                 map[sarr[left]]! += 1
45                 left += 1
46             }            
47         }        
48         return result
49     }    
50 }

132ms

 1 class Solution {
 2     
 3     let charToIntMap: [Character: Int] = [
 4         "a": 0,
 5         "b": 1,
 6         "c": 2,
 7         "d": 3,
 8         "e": 4,
 9         "f": 5,
10         "g": 6,
11         "h": 7,
12         "i": 8,
13         "j": 9,
14         "k": 10,
15         "l": 11,
16         "m": 12,
17         "n": 13,
18         "o": 14,
19         "p": 15,
20         "q": 16,
21         "r": 17,
22         "s": 18,
23         "t": 19,
24         "u": 20,
25         "v": 21,
26         "x": 22,
27         "w": 23,
28         "y": 24,
29         "z": 25
30     ]
31     
32     
33     func findAnagrams(_ s: String, _ p: String) -> [Int] {
34         guard s.count >= p.count else { return [Int]() }
35         var i = 0
36         var j = 0
37         let sArr = Array(s)
38         let pArr = Array(p)
39         
40         var pInt = Array<Int>(repeating: 0, count: 26)
41         var ans = [Int]()
42         
43         for ch in pArr {
44             pInt[charToIntMap[ch]!] = pInt[charToIntMap[ch]!] + 1
45         }
46         var movingInt = Array<Int>(repeating: 0, count: 26)
47         while i < sArr.count && j < pArr.count {
48             let ch = sArr[i]
49             movingInt[charToIntMap[ch]!] = movingInt[charToIntMap[ch]!] + 1 
50             i += 1
51             j += 1
52         }
53         if movingInt == pInt {
54             ans.append(0)
55         }
56         while i < sArr.count {
57             let ch = sArr[i]
58             let prevCh = sArr[i - j]
59             movingInt[charToIntMap[ch]!] = movingInt[charToIntMap[ch]!] + 1 
60             movingInt[charToIntMap[prevCh]!] = movingInt[charToIntMap[prevCh]!] - 1 
61             if movingInt == pInt {
62                 ans.append(i - j + 1)
63             }
64             i += 1
65         }
66         return ans
67     }
68 }

164ms

 1 class Solution {
 2     func findAnagrams(_ s: String, _ p: String) -> [Int] {
 3         guard s.count >= p.count else { return [] }
 4         let sChars = Array(s.characters.map { String($0).uppercased() })
 5         let pChars = Array(p.characters.map { String($0).uppercased() })
 6         var result = [Int]()
 7         var pCount = Array(repeating: 0, count: 26)
 8         var windowCount = Array(repeating: 0, count: 26)
 9         
10         for i in 0..<pChars.count {
11             pCount[Int(UnicodeScalar(pChars[i])!.value) - Int(UnicodeScalar("A")!.value)] += 1
12             windowCount[Int(UnicodeScalar(sChars[i])!.value) - Int(UnicodeScalar("A")!.value)] += 1
13         }
14         
15         for i in pChars.count..<sChars.count {
16             if compareArrays(pCount, windowCount) { result.append(i - pChars.count) }
17             
18             windowCount[Int(UnicodeScalar(sChars[i - pChars.count])!.value) - Int(UnicodeScalar("A")!.value)] -= 1
19             windowCount[Int(UnicodeScalar(sChars[i])!.value) - Int(UnicodeScalar("A")!.value)] += 1
20         }
21         
22         if compareArrays(pCount, windowCount) { result.append(sChars.count - pChars.count) }
23         
24         return result
25     }
26     
27     func compareArrays(_ a: [Int], _ b: [Int]) -> Bool {
28         guard a.count == b.count else { return false }
29         for i in 0..<a.count {
30             if a[i] != b[i] { return false }
31         }
32         return true
33     }
34 }

Runtime: 1776 ms

Memory Usage: 20.5 MB

 1 class Solution {
 2     func findAnagrams(_ s: String, _ p: String) -> [Int] {
 3         if s.isEmpty || p.count > s.count {return []}
 4         var res:[Int] = [Int]()
 5         var m1:[Int] = [Int](repeating:0,count:256)
 6         var m2:[Int] = [Int](repeating:0,count:256)
 7         var arrS = Array(s).map{$0.ascii}
 8         var arrP = Array(p).map{$0.ascii}
 9         for i in 0..<p.count
10         {
11             m1[arrS[i]] += 1
12             m2[arrP[i]] += 1
13         }
14         if m1 == m2
15         {
16             res.append(0)
17         }
18         for i in p.count..<s.count
19         {
20             m1[arrS[i]] += 1
21             m1[arrS[i - p.count]] -= 1
22             if m1 == m2
23             {
24                 res.append(i - p.count + 1)
25             }
26         }
27         return res
28     }
29 }
30 
31 extension Character  
32 {  
33   //属性：ASCII整数值(定义小写为整数值)
34    var ascii: Int {
35         get {
36             let s = String(self).unicodeScalars
37             return Int(s[s.startIndex].value)
38         }
39     }
40 }