Discussion on: Daily Challenge #182 - Arrh, grabscrab!

View post

Python, two solutions:

Both solutions grow linearly as the number of words in the dictionary grows (we make a single pass through the dictionary and compare if it is an anagram).

Calling anagram_Onlogn multiplies O(n*log(n)) to the runtime, where n is the length of words. This is because it uses sorting to compare words ==> O(dictionary_size * word_size * log(word_size))

Calling anagram_On multiples O(word_size) to the runtime since we use hashmaps (python dicts) to compare words linearly on their size ==> O(dictionary_size * word_size)

def grabscrab(jumble,  dictionary):
  words = []
  for word in dictionary:
    if anagram_On(jumble, word):
      words.append(word)
  return words

# n*log(n) comparison -  better than n^2 but worse than n
def anagram_Onlogn(worda, wordb):
  alist = list(worda)
  blist = list(wordb)
  alist.sort()
  blist.sort()
  return (alist == blist)

# optimal comparison  - we  can't do better than linear since we have to at least read each letter
def anagram_On(worda, wordb):
  adict = make_dict(worda)
  bdict = make_dict(wordb)
  return adict == bdict

def make_dict(word):
  d = {}
  for letter in word:
    if letter not in d:
      d[letter] = 0
    d[letter] += 1
  return d

print(grabscrab("ortsp", ["sport", "parrot", "ports", "matey"]))
print(grabscrab("trisf", ["first"]))
print(grabscrab("oob", ["bob", "baobab"]))
print(grabscrab("ainstuomn", ["mountains", "hills", "mesa"]))
print(grabscrab("oolp", ["donkey", "pool", "horse", "loop"]))