Monday, October 13, 2014

Another anagram

It's been a little while since I've practiced solving smaller problems with the idea of improving my coding skills. (For a couple of weeks I became an in-house dog-sitter for a small puppy; who knew small puppies are SO demanding of attention).

The problem asks to take a parent string and a child string as parameters, and return the count of how many times a child string appears in the parent string as is or as an anagram.

I first tried to create all the permutations within the parent string but realized it was a wrong approach (to begin with, it took forever).

My final solution involves sorting a child string first. While iterating a parent string, at each iteration I create a string of the length of the child and sort it as well. Then I compare the child to this newly created string and increment the counter if the two match.

def anagram_detection(parent, child)
    sorted_child = child.chars.sort.join
    char_parent = parent.chars
    counter = 0
    (0..char_parent.length - child.length).each do |i|
        word = char_parent[i...i+child.length].sort.join
        counter += 1 if sorted_child == word
    end
    counter
end

print anagram_detection('AdnBndAndBdaBn', 'dAn')
print anagram_detection('AbrAcadAbRa', 'cAda')

No comments :

Post a Comment