[swift] LeetCode 438. Find All Anagrams in a String

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 p will 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”.

func findAnagrams(_ s: String, _ p: String) -> [Int] {
    let n = p.count
    var arr = Array(repeating: 0, count: s.count) , i = 0, c: Character, j = 0

    var pArr = Array(repeating: 0, count: 26)
    p.utf8.forEach({ pArr[Int($0-97)] += 1 })
    let pSet = pArr.enumerated().filter({$0.element > 0}).map({ Character(UnicodeScalar($0.offset + 97)!)  })

    while i + n <= s.count {
        let start = s.index(s.startIndex, offsetBy: i)
        let end = s.index(s.startIndex, offsetBy: i + n)
        c = s[start]
        let t = s[start..<end]

        var tArr = Array(repeating: 0, count: 26)
        t.utf8.forEach({ tArr[Int($0-97)] += 1 })

        if tArr == pArr {
            arr[j] = i; j += 1
            while i + n < s.count {
                let c1 = s[s.index(s.startIndex, offsetBy: i + n)]
                if c == c1 {
                    i += 1
                    c = s[s.index(s.startIndex, offsetBy: i)]
                    arr[j] = i; j += 1
                } else if !pSet.contains(c1) {
                    i += n; break
                } else {
                    break
                }
            }
        }
        i += 1
    }

    return Array(arr[0..<j])
}

func findAnagrams(_ s: String, _ p: String) -> [Int] {

let n = p.count

var arr = Array(repeating: 0, count: s.count) , i = 0, c: Character, j = 0

var pArr = Array(repeating: 0, count: 26)

p.utf8.forEach({ pArr[Int($0-97)] += 1 })

let pSet = pArr.enumerated().filter({$0.element > 0}).map({ Character(UnicodeScalar($0.offset + 97)!) })

while i + n <= s.count {

let start = s.index(s.startIndex, offsetBy: i)

let end = s.index(s.startIndex, offsetBy: i + n)

c = s[start]

let t = s[start..<end]

var tArr = Array(repeating: 0, count: 26)

t.utf8.forEach({ tArr[Int($0-97)] += 1 })

if tArr == pArr {

arr[j] = i; j += 1

while i + n < s.count {

let c1 = s[s.index(s.startIndex, offsetBy: i + n)]

if c == c1 {

i += 1

c = s[s.index(s.startIndex, offsetBy: i)]

arr[j] = i; j += 1

} else if !pSet.contains(c1) {

i += n; break

} else {

break

}

i += 1

}

return Array(arr[0..<j])

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版