Clash Royale CLAN TAG#URR8PPP

How to search for anagrams in O(logN) time given an input from the user?

Hi I've been thinking of how to implement this for days.

I'm trying to implement a programme that reads a dictionary into a list and sorts it in O(N) time.After that, I have to search for the anagrams in the list given an input from the user in O(log N) time.I can sort each word by letter and sort the list alphabetically in O(N).

Since I'm trying to search in O(logN) time, I tried to use binary search by sorting every letter in each word and using that as a key to identify the anagrams.
For example 'act' is the key for anagram group 'act,'cat','tac'.

arr=['act','cat','tac','bad','fad']


After sorting

[['act', 'act'], ['cat', 'act'], ['tac', 'act'], ['bad', 'abd'], ['fad', 'adf']]


But binary search only finds ONE target so it will only return 'tac' for anagram group under 'act'.My binary search code:

def binarySearch(arr, lower, upper, target):
anagramList=
if upper >= lower:
mid = lower + ((upper - lower) // 2)
if areAnagrams(arr[mid][1],target):
anagramList.append(arr[mid])
elif arr[mid] > target:
return binarySearch(arr, lower, mid - 1, target)
else:
return binarySearch(arr, mid + 1, upper, target)
return anagramList


I tried to group them like this

[['act','act','cat','tac'],['bad','abd'],['fad','daf]]


but it takes O(N^2) complexity which is larger than O(N)?Can anyone suggest how I should go about this?Thanks.

Edit:
For example, if the query string is alppe, the output will consist of the words appel, and apple.

2 Answers
2

You will need to use Counter from collections module. The Counter class is not hashable so we will make it hashable dict from it.

from collections import Counter, defaultdict


class hashablecounter(Counter):
def __hash__(self):
return hash(tuple(sorted(self.items())))


d = defaultdict(list)
arr=['act','cat','tac','bad','fad']

for a in arr:
d[hashablecounter(a)].append(a)

s = 'cat'
print('Anagrams for ', s, ' are ', d[hashablecounter(s)])


You can use a dictionary with the key being the word with letters sorted.

from collections import defaultdict
anagrams = defaultdict(list)

arr=['act','cat','tac','bad','fad']

for word in arr:
anagrams[''.join(sorted(word))].append(word)

def get_anagram(user_input):
return anagrams[''.join(sorted(user_input))]


Example:

>>> get_anagram('tca')
['act', 'cat', 'tac']


N

arr

O(n)

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.