Wednesday, October 04, 2017

anagram substring search

[] 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