Leetcode Answers 438

接下来是一道Easy题,是和Sliding Window有关。

题目:
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:

1
2
3
4
5
6
7
8
9
**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:

1
2
3
4
5
6
7
8
9
10
**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".

思路:
这是一道典型的sliding window的题,即在string s 上放一个sliding window,一点一点挪动来判断是否是string p 的anagram。前面的题也提到了如何判断两个string是否互为anagram,即用一个int[]来当map。这里因为还有一个sliding的问题,每一次重新计算全部的元素太麻烦了,所以就用替代法,用一个sum值来判断,并用去头加尾的方式来slide,而一旦遇到没见过的char就可以跳到下一个index重新开始了。

Answer:

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
public class Solution {
public IList<int> FindAnagrams(string s, string p) {
int len = p.Length;
int lon = s.Length;
var ret = new List<int>();
if(lon < len)
return ret;
var chars = new int[26];
int sum = 0;
for(int i=0;i<len;++i){
sum+=p[i]-'a';
++chars[p[i]-'a'];
}
int sum1 = 0;
int startidx = 0;
for(int endidx = 0; endidx < lon; endidx++){
if(chars[s[endidx]-'a'] == 0){
sum1 = 0;
startidx = endidx+1;
continue;
}
sum1+= s[endidx] - 'a';
if(endidx - startidx + 1 == len){
if(sum1 == sum) ret.Add(startidx);
sum1 -= s[startidx++]-'a';
}
}
return ret;
}
}

考察:第一眼直观的brutal force就是写一个isAnagram的函数,从s的头开始找substring和p一起传进去,然而这个是会很轻易就TLE的,毕竟时间复杂度是O(n^2)左右。所以必然要用sliding window来减少重复计算。

以上。

17-04-27
@Sturbridge