Slide window: 438. Find all letter heterotopic words in string

/ * *

The title

Given a string s and a non-empty string p, find all substrings of the alphabetic alloword p in S and return the starting index of these substrings.

The string contains only lowercase letters, and the length of the string s and p cannot exceed 20100.

Description:

An anagram is a string with the same letters but different arrangements. Regardless of the order in which the answers are printed. Example 1:

Enter: s: “cbaebabacd” p: “ABC”

Output: [0, 6]

Explanation: The substring whose starting index is 0 is “CBA “, which is an anagram of” ABC “. The substring whose starting index is 6 is “bac”, which is an anagram of “ABC”. Example 2:

Enter: s: “abab” p: “ab”

Output: [0, 1, 2]

Explanation: the substring whose starting index equals 0 is “ab”, which is an alphabetic allotopic of “ab”. The substring whose starting index equals 1 is “ba”, which is an anagram of “ab”. The substring whose starting index equals 2 is “ab”, which is an alphabetic allotopic of “ab”.

Source: LeetCode link: leetcode-cn.com/problems/fi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The test code

print(findAnagrams(“cbaebabacd”, “abc”))

notes

The first is that the window contains the letters of the target string and the second is that the length of the window is equal to the length of the target string

When I first started doing this, I thought about a lot of things like what do I do when I have characters that are not in the target string what do I do when I have more than the target string in the loop

But you don’t have to, you just follow the idea of sliding Windows by following two conditions: the right boundary moves back when the conditions are not met and the left boundary moves back when the conditions are met

The code address

Github.com/zmfflying/Z… * /

The problem solving code

import Foundation func findAnagrams(_ s: String, _ p: String) -> [Int] {if s.ount < p.ount {return []} var res:[Int] = [Int]( Var dicP:[Character: Int] = [Character: Int] = [Character: Int Int]() for c in arrP { dicP[c] = dicP[c] == nil ? 1 : (dicP[c]! Var dicWindow:[Character: Int] = [Character: Int]() var start: Int = 0 var end: Int = 0 var match = 0 while end < arrS. Count {let c = arrS[end dicWindow[c] == nil { dicWindow[c] = 1 } else { let newCount = dicWindow[c]! If pCount = dicP[c] {if pCount == dicWindow[c] {if pCount == dicWindow[c] { Abdc -> ABC while match == dicp. count {// match += 1}} If end-start + 1 == arrp. count {res.append(start)} let cStart: if end-start + 1 == arrp. count {res.append(start)} let cStart: Character = arrS[start] let curCount = dicWindow[cStart]! If curCount == dicP[cStart] {match -= 1} if curCount == dicP[cStart] {match -= 1} DicWindow [cStart] = curCount -1 start += 1} dicWindow[cStart] = curCount -1 start += 1} end += 1} return res}Copy the code