438.Find All Anagrams in a String¶
Tags: Medium
Two Pinters
Hash Table
Links: https://leetcode.com/problems/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".
虽然官方给的标签是Hash Table
,但是一般限制都是小写字母的时候,可以不用哈希表,而是用一个长度为26的数组来代替,这样速度会快很多。
本题题意是考虑给定的模式串p
,先用pattern
统计出每个字符的频率,因为题目限定不用考虑顺序,如果考虑顺序,那就是KMP了。
双指针维护长度为p
的窗口,每次start
和end
往前移动一个位置,相应的需要减去被去掉的start
和增加的end
,在增加end
的时候,需要判断是否还在字符串的范围内。
比较两个字符频率数组时间复杂度是O(1),总的时间复杂度是O(1),空间复杂度是O(1)。