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
- 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".
- 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".
C Solution:
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
void save(int **res, int *size, int *returnSize, int val) {
if (*size == *returnSize) {
*size += 1000;
*res = realloc(*res, *size * sizeof(int));
}
(*res)[(*returnSize)++] = val;
}
int* findAnagrams(char* s, char* p, int* returnSize) {
if (strlen(s) < strlen(p)) return 0;
int size = 1000;
int *res = malloc(size * sizeof(int));
*returnSize = 0;
int i, diff = 0, flag[256] = {0};
for (i = 0; p[i]; i++) {
if (s[i] == p[i]) continue;
diff += ++flag[s[i]] > 0 ? 1 : -1;
diff += --flag[p[i]] < 0 ? 1 : -1;
}
if (!diff) save(&res, &size, returnSize, 0);
int j;
for (j = i; s[j]; j++) {
diff += ++flag[s[j]] > 0 ? 1 : -1;
diff += --flag[s[j - i]] < 0 ? 1 : -1;
if (!diff) save(&res, &size, returnSize, j - i + 1);
}
return res;
}
Python Solution 1:
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
if len(s) < len(p): return []
d = collections.Counter(p)
diff = len(p)
res = []
for i in range(len(p)):
if d[s[i]] > 0:
diff -= 1
else:
diff += 1
d[s[i]] -= 1
if not diff: res.append(0)
for i in range(len(p), len(s)):
if d[s[i]] > 0:
diff -= 1
else:
diff += 1
d[s[i]] -= 1
if d[s[i - len(p)]] < 0:
diff -= 1
else:
diff += 1
d[s[i - len(p)]] += 1
if not diff: res.append(i - len(p) + 1)
return res
Python Solution 2:
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
if not s or not p or len(s) < len(p): return []
d = collections.Counter(p)
diff = len(p)
res = []
for i in range(len(p)):
c = s[i]
diff += 1 if d[c] <= 0 else -1
d[c] -= 1
if not diff: res.append(0)
for i in range(len(p), len(s)):
c = s[i]
diff += 1 if d[c] <= 0 else -1
d[c] -= 1
c = s[i - len(p)]
diff += 1 if d[c] >= 0 else -1
d[c] += 1
if not diff: res.append(i - len(p) + 1)
return res
Python Solution 3:
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
if not s or not p or len(s) < len(p): return []
res = []
pp = collections.Counter(p)
ss = collections.Counter(s[:len(p)])
if ss == pp: res.append(0)
for i in range(len(p), len(s)):
c = s[i]
ss[c] += 1
c = s[i - len(p)]
if ss[c] == 1: del ss[c]
else: ss[c] -= 1
if ss == pp: res.append(i - len(p) + 1)
return res
Summary:
- 16ms, 76.74%
- Maybe anagram problems can all use this idea: use a diff, one direction for add, the other for del.
- Similar to 242. Valid Anagram
LeetCode: 438. Find All Anagrams in a String
近期评论