647. 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 40,000.
The order of output does not matter.
Example
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".
class Solution:
"""
@param s: a string
@param p: a string
@return: a list of index
"""
def findAnagrams(self, s, p):
# write your code here
result = []
possible ={}
windows= {}
length = len(p)
for each in range(len(p)):
if possible.get(p[each]):
possible[p[each]] = possible.get(p[each]) +1
else:
possible[p[each]] = 1
print (possible)
for each in s[0:length]:
if windows.get(each) is not None :
windows[each] = windows.get(each) +1
else:
windows[each] = 1
for i in range(len(s)-length+1):
print('window = ' + str(windows))
print('possible = ' + str(possible))
if windows == possible:
result.append(i)
print(s[i])
print(windows.get(s[i]))
if windows.get(s[i]) == 1:
windows.pop(s[i])
else:
windows[s[i]] = windows.get(s[i]) -1
if i+length < len(s) and windows.get(s[i+length]):
windows[s[i+length]] = windows.get(s[i+length]) +1
elif i+length< len(s):
windows[s[i+length]] = 1
return result
领扣对结果审查更加严格 在leetcode上可以过的 方法 均超时
class Solution:
"""
@param s: a string
@param p: a string
@return: a list of index
"""
def findAnagrams(self, s, p):
# write your code here
result = []
length = len(p)
#print (possible)
p = ''.join(sorted(p))
for i in range(len(s)-length+1):
#print ("p = " + str(p))
#print ("s[i:length+i] = " + str(''.join(sorted(s[i:length+i]))))
if ''.join(sorted(s[i:length+i])) == p:
result.append(i)
return result
class Solution:
"""
@param s: a string
@param p: a string
@return: a list of index
"""
def findAnagrams(self, s, p):
# write your code here
result = []
possible ={}
for each in range(len(p)):
if possible.get(p[each]):
possible[p[each]] = possible.get(p[each]) +1
else:
possible[p[each]] = 1
#print (possible)
length = len(p)
for i in range(len(s)):
temp = possible.copy()
for each in s[i:i+length]:
print (temp.get(each))
if temp.get(each) is not None and temp[each]> 1:
temp[each]= temp.get(each) - 1
elif temp.get(each) is not None:
temp.pop(each)
if len(temp) == 0:
result.append(i)
return result
原因是其中有一个p等于10001个字符 直接超出array大小 且不能sort
Input
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa ...
Input Data
Expected
[0,10001]
请登录之后再进行评论