Given two arrays of strings, for every string in list, determine how many anagrams of it are in the other list. How to increase time efficiency?

user_13628295 0
Viewed 2946

Problem : Given two arrays of strings, for every string in list (query), determine how many anagrams of it are in the other list (dictionary).
It should return an array of integers.
Example:
query = ["a", "nark", "bs", "hack", "stair"]
dictionary = ['hack', 'a', 'rank', 'khac', 'ackh', 'kran', 'rankhacker', 'a', 'ab', 'ba', 'stairs', 'raits']
The answer would be [2, 2, 0, 3, 1]
since query[0] = 'a' has 2 anagrams in dictionary: 'a' and 'a' and so on...
This was the most efficient code I could come up with:

d = {'a': 2, 'b': 3, 'c': 5, 'd': 7, 'e': 11, 'f': 13, 'g': 17, 'h': 19, 'i': 23, 'j': 29, 'k': 31, 'l': 37, 'm': 41, 'n': 43, 'o': 47, 'p': 53, 'q': 59, 'r': 61, 's': 67, 't': 71, 'u': 73, 'v': 79, 'w': 83, 'x': 89, 'y': 97, 'z': 101}
def number(a):
    prod = 1
    for i in a:
        prod *= d[i]
    return prod

def stringAnagram(dictionary, query):
    for i in range(len(query)):
        query[i] = number(query[i])
    for j in range(len(dictionary)):
        dictionary[j] = number(dictionary[j])
    dictionary.sort()
    ans = []
    k = len(dictionary)
    for i in query:
        j = 0
        num = 0
        while j < k and dictionary[j] <= i:
            if dictionary[j] == i:
                num += 1
            j += 1
        ans.append(num)
    return ans

The code was showing time out for large inputs. Is there any way to improve the time efficiency (decrease the time complexity) of the code?

time-complexity python-3.x algorithm python performance
1 Answers

You can just sort every word in the dictionary as well as every word in the query.
Since we have just 26 possible characters in a word, count sort would work best.

So your example would become:

query = ["a", "aknr", "bs", "achk", "airst"]
dictionary = ['achk', 'a', 'aknr', 'achk', 'achk', 'aknr', ... 'airst']

Then just create a hashmap of word vs count of the dictionary array.

a -> 2
ab -> 2
airts -> 2
...
...

Now iterate through every (sorted) word in query and check how many times it occurs in the hashmap.

ans = []
for sorted_word in query:
    num = dict_hashmap.get(sorted_word, 0)
    ans.append(num)

Assuming:

  • w is the average length of a word.
  • n is the number of words in query.
  • m is the number of words in dictionary.

Complexity analysis:

  1. Sorting every word = O(w * (n + m)).
  2. Creating hashmap of dictionary = O(w * m).
  3. Iterating through query and using hashmap to get answer = O(w * n).

Complexity = O(w * (n + m))

This is the most efficient algorithm possible for this problem (linearly proportional to the total number of input characters).

user_19253880
Related