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]
请登录之后再进行评论