[] getAllAnagrams(text, pattern):
if text == null || pattern == null:
throw
if pattern == "":
throw
if pattern.length() > text.length():
return []
patternmap = (pattern)
wmap = new
for i = 0, i < text.length(), i++:
// drop from wmap
dropi = i -pattern.length()
if dropi >= 0:
dropc = text[dropi]
if --smap[dropc] == 0:
wmap.removekey(dropc)
// add to wmap
c = text[i]
if !wmap.haskey(c):
wmap[c] = 0
wmap[c]++
// check if anagram
if i +1 >= pattern.length() && isanagram(wmap, patternmap):
anagrams.add(text.substring(i -pattern.length() +1, pattern.length())
return anagrams
bool isanagram(wmap, patternmap):
if wmap.keys.count != patternmap.keys.count():
return false
for c in wmap.keys():
if !patternmap.haskey(c) || patternmap[c] != wmap[c]:
return false
return true
map tomap(s):
map = new
for c in s:
if !map.haskey(c):
map[c] = 0
map[c]++
return map
012345
abcdeabdca
|--i
[Hat tip to GfG, AP]
No comments:
Post a Comment