给定两个字符串 s 和 p，找到 s ** ** 中所有 p ** ** 的 **异位词
**的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 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" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104s 和 p 仅包含小写字母
方法一：滑动窗口
思路
根据题目要求，我们需要在字符串 $s$ 寻找字符串 $p$ 的异位词。因为字符串 $p$ 的异位词的长度一定与字符串 $p$ 的长度相同，所以我们可以在字符串 $s$ 中构造一个长度为与字符串 $p$ 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 $p$ 中每种字母的数量相同时，则说明当前窗口为字符串 $p$ 的异位词。
算法
在算法的实现中，我们可以使用数组来存储字符串 $p$ 和滑动窗口中每种字母的数量。
细节
当字符串 $s$ 的长度小于字符串 $p$ 的长度时，字符串 $s$ 中一定不存在字符串 $p$ 的异位词。但是因为字符串 $s$ 中无法构造长度与字符串 $p$ 的长度相同的窗口，所以这种情况需要单独处理。
代码
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
s_len, p_len = len(s), len(p)
if s_len < p_len:
return []
ans = []
s_count = [0] * 26
p_count = [0] * 26
for i in range(p_len):
s_count[ord(s[i]) - 97] += 1
p_count[ord(p[i]) - 97] += 1
if s_count == p_count:
ans.append(0)
for i in range(s_len - p_len):
s_count[ord(s[i]) - 97] -= 1
s_count[ord(s[i + p_len]) - 97] += 1
if s_count == p_count:
ans.append(i + 1)
return ans
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
int[] sCount = new int[26];
int[] pCount = new int[26];
for (int i = 0; i < pLen; ++i) {
++sCount[s.charAt(i) - 'a'];
++pCount[p.charAt(i) - 'a'];
}
if (Arrays.equals(sCount, pCount)) {
ans.add(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
--sCount[s.charAt(i) - 'a'];
++sCount[s.charAt(i + pLen) - 'a'];
if (Arrays.equals(sCount, pCount)) {
ans.add(i + 1);
}
}
return ans;
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| public class Solution {
public IList<int> FindAnagrams(string s, string p) {
int sLen = s.Length, pLen = p.Length;
if (sLen < pLen) {
return new List<int>();
}
IList<int> ans = new List<int>();
int[] sCount = new int[26];
int[] pCount = new int[26];
for (int i = 0; i < pLen; ++i) {
++sCount[s[i] - 'a'];
++pCount[p[i] - 'a'];
}
if (Enumerable.SequenceEqual(sCount, pCount)) {
ans.Add(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
--sCount[s[i] - 'a'];
++sCount[s[i + pLen] - 'a'];
if (Enumerable.SequenceEqual(sCount, pCount)) {
ans.Add(i + 1);
}
}
return ans;
}
}
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int sLen = s.size(), pLen = p.size();
if (sLen < pLen) {
return vector<int>();
}
vector<int> ans;
vector<int> sCount(26);
vector<int> pCount(26);
for (int i = 0; i < pLen; ++i) {
++sCount[s[i] - 'a'];
++pCount[p[i] - 'a'];
}
if (sCount == pCount) {
ans.emplace_back(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
--sCount[s[i] - 'a'];
++sCount[s[i + pLen] - 'a'];
if (sCount == pCount) {
ans.emplace_back(i + 1);
}
}
return ans;
}
};
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func findAnagrams(s, p string) (ans []int) {
sLen, pLen := len(s), len(p)
if sLen < pLen {
return
}
var sCount, pCount [26]int
for i, ch := range p {
sCount[s[i]-'a']++
pCount[ch-'a']++
}
if sCount == pCount {
ans = append(ans, 0)
}
for i, ch := range s[:sLen-pLen] {
sCount[ch-'a']--
sCount[s[i+pLen]-'a']++
if sCount == pCount {
ans = append(ans, i+1)
}
}
return
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| var findAnagrams = function(s, p) {
const sLen = s.length, pLen = p.length;
if (sLen < pLen) {
return [];
}
const ans = [];
const sCount = new Array(26).fill(0);
const pCount = new Array(26).fill(0);
for (let i = 0; i < pLen; ++i) {
++sCount[s[i].charCodeAt() - 'a'.charCodeAt()];
++pCount[p[i].charCodeAt() - 'a'.charCodeAt()];
}
if (sCount.toString() === pCount.toString()) {
ans.push(0);
}
for (let i = 0; i < sLen - pLen; ++i) {
--sCount[s[i].charCodeAt() - 'a'.charCodeAt()];
++sCount[s[i + pLen].charCodeAt() - 'a'.charCodeAt()];
if (sCount.toString() === pCount.toString()) {
ans.push(i + 1);
}
}
return ans;
};
|
复杂度分析
时间复杂度：$O(m + (n-m) \times \Sigma)$，其中 $n$ 为字符串 $s$ 的长度，$m$ 为字符串 $p$ 的长度，$\Sigma$ 为所有可能的字符数。我们需要 $O(m)$ 来统计字符串 $p$ 中每种字母的数量；需要 $O(m)$ 来初始化滑动窗口；需要判断 $n-m+1$ 个滑动窗口中每种字母的数量是否与字符串 $p$ 中每种字母的数量相同，每次判断需要 $O(\Sigma)$ 。因为 $s$ 和 $p$ 仅包含小写字母，所以 $\Sigma = 26$。
空间复杂度：$O(\Sigma)$。用于存储字符串 $p$ 和滑动窗口中每种字母的数量。
方法二：优化的滑动窗口
思路和算法
在方法一的基础上，我们不再分别统计滑动窗口和字符串 $p$ 中每种字母的数量，而是统计滑动窗口和字符串 $p$ 中每种字母数量的差；并引入变量 differ 来记录当前窗口与字符串 $p$ 中数量不同的字母的个数，并在滑动窗口的过程中维护它。
在判断滑动窗口中每种字母的数量与字符串 $p$ 中每种字母的数量是否相同时，只需要判断 differ 是否为零即可。
代码
[sol2-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
s_len, p_len = len(s), len(p)
if s_len < p_len:
return []
ans = []
count = [0] * 26
for i in range(p_len):
count[ord(s[i]) - 97] += 1
count[ord(p[i]) - 97] -= 1
differ = [c != 0 for c in count].count(True)
if differ == 0:
ans.append(0)
for i in range(s_len - p_len):
if count[ord(s[i]) - 97] == 1:
differ -= 1
elif count[ord(s[i]) - 97] == 0:
differ += 1
count[ord(s[i]) - 97] -= 1
if count[ord(s[i + p_len]) - 97] == -1:
differ -= 1
elif count[ord(s[i + p_len]) - 97] == 0:
differ += 1
count[ord(s[i + p_len]) - 97] += 1
if differ == 0:
ans.append(i + 1)
return ans
|
[sol2-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
int[] count = new int[26];
for (int i = 0; i < pLen; ++i) {
++count[s.charAt(i) - 'a'];
--count[p.charAt(i) - 'a'];
}
int differ = 0;
for (int j = 0; j < 26; ++j) {
if (count[j] != 0) {
++differ;
}
}
if (differ == 0) {
ans.add(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
if (count[s.charAt(i) - 'a'] == 1) {
--differ;
} else if (count[s.charAt(i) - 'a'] == 0) {
++differ;
}
--count[s.charAt(i) - 'a'];
if (count[s.charAt(i + pLen) - 'a'] == -1) {
--differ;
} else if (count[s.charAt(i + pLen) - 'a'] == 0) {
++differ;
}
++count[s.charAt(i + pLen) - 'a'];
if (differ == 0) {
ans.add(i + 1);
}
}
return ans;
}
}
|
[sol2-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| public class Solution {
public IList<int> FindAnagrams(string s, string p) {
int sLen = s.Length, pLen = p.Length;
if (sLen < pLen) {
return new List<int>();
}
IList<int> ans = new List<int>();
int[] count = new int[26];
for (int i = 0; i < pLen; ++i) {
++count[s[i] - 'a'];
--count[p[i] - 'a'];
}
int differ = 0;
for (int j = 0; j < 26; ++j) {
if (count[j] != 0) {
++differ;
}
}
if (differ == 0) {
ans.Add(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
if (count[s[i] - 'a'] == 1) {
--differ;
} else if (count[s[i] - 'a'] == 0) {
++differ;
}
--count[s[i] - 'a'];
if (count[s[i + pLen] - 'a'] == -1) {
--differ;
} else if (count[s[i + pLen] - 'a'] == 0) {
++differ;
}
++count[s[i + pLen] - 'a'];
if (differ == 0) {
ans.Add(i + 1);
}
}
return ans;
}
}
|
[sol2-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int sLen = s.size(), pLen = p.size();
if (sLen < pLen) {
return vector<int>();
}
vector<int> ans;
vector<int> count(26);
for (int i = 0; i < pLen; ++i) {
++count[s[i] - 'a'];
--count[p[i] - 'a'];
}
int differ = 0;
for (int j = 0; j < 26; ++j) {
if (count[j] != 0) {
++differ;
}
}
if (differ == 0) {
ans.emplace_back(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
if (count[s[i] - 'a'] == 1) {
--differ;
} else if (count[s[i] - 'a'] == 0) {
++differ;
}
--count[s[i] - 'a'];
if (count[s[i + pLen] - 'a'] == -1) {
--differ;
} else if (count[s[i + pLen] - 'a'] == 0) {
++differ;
}
++count[s[i + pLen] - 'a'];
if (differ == 0) {
ans.emplace_back(i + 1);
}
}
return ans;
}
};
|
[sol2-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| func findAnagrams(s, p string) (ans []int) {
sLen, pLen := len(s), len(p)
if sLen < pLen {
return
}
count := [26]int{}
for i, ch := range p {
count[s[i]-'a']++
count[ch-'a']--
}
differ := 0
for _, c := range count {
if c != 0 {
differ++
}
}
if differ == 0 {
ans = append(ans, 0)
}
for i, ch := range s[:sLen-pLen] {
if count[ch-'a'] == 1 {
differ--
} else if count[ch-'a'] == 0 {
differ++
}
count[ch-'a']--
if count[s[i+pLen]-'a'] == -1 {
differ--
} else if count[s[i+pLen]-'a'] == 0 {
differ++
}
count[s[i+pLen]-'a']++
if differ == 0 {
ans = append(ans, i+1)
}
}
return
}
|
[sol2-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| var findAnagrams = function(s, p) {
const sLen = s.length, pLen = p.length;
if (sLen < pLen) {
return [];
}
const ans = [];
const count = Array(26).fill(0);
for (let i = 0; i < pLen; ++i) {
++count[s[i].charCodeAt() - 'a'.charCodeAt()];
--count[p[i].charCodeAt() - 'a'.charCodeAt()];
}
let differ = 0;
for (let j = 0; j < 26; ++j) {
if (count[j] !== 0) {
++differ;
}
}
if (differ === 0) {
ans.push(0);
}
for (let i = 0; i < sLen - pLen; ++i) {
if (count[s[i].charCodeAt() - 'a'.charCodeAt()] === 1) {
--differ;
} else if (count[s[i].charCodeAt() - 'a'.charCodeAt()] === 0) {
++differ;
}
--count[s[i].charCodeAt() - 'a'.charCodeAt()];
if (count[s[i + pLen].charCodeAt() - 'a'.charCodeAt()] === -1) {
--differ;
} else if (count[s[i + pLen].charCodeAt() - 'a'.charCodeAt()] === 0) {
++differ;
}
++count[s[i + pLen].charCodeAt() - 'a'.charCodeAt()];
if (differ === 0) {
ans.push(i + 1);
}
}
return ans;
};
|
复杂度分析
时间复杂度：$O(n+m+\Sigma)$，其中 $n$ 为字符串 $s$ 的长度，$m$ 为字符串 $p$ 的长度，其中$\Sigma$ 为所有可能的字符数。我们需要 $O(m)$ 来统计字符串 $p$ 中每种字母的数量；需要 $O(m)$ 来初始化滑动窗口；需要 $O(\Sigma)$ 来初始化 differ；需要 $O(n-m)$ 来滑动窗口并判断窗口内每种字母的数量是否与字符串 $p$ 中每种字母的数量相同，每次判断需要 $O(1)$ 。因为 $s$ 和 $p$ 仅包含小写字母，所以 $\Sigma = 26$。
空间复杂度：$O(\Sigma)$。用于存储滑动窗口和字符串 $p$ 中每种字母数量的差。
