Number of occurrences of strings in array

Question

This is a Hackerrank problem (https://www.hackerrank.com/challenges/sparse-arrays/problem).

We're given an array of strings and an array of queries, and have to return an array of the number of occurrences of each query in the array of strings. For example: s = ['ab', 'abc', 'aba', 'ab']. q = ['ab', atr', 'abc]. We need to return [2, 0, 1].

The constraints are 1 <= n <= 1000, 1 <= q <= 1000, where n and q are the number of strings and queries respectively, and 1 <= |strings[i]|, |queries[i]| <= 20.

Here is my code:

def matchingStrings(strings, queries):
    results = []
    dic = {q:0 for q in queries}
    for s in strings:
        if s in dic: dic[s] += 1
    for q in queries:
        if q in dic: results.append(dic[q]) 
    return results

Is there anything I can optimize? Speed, memory usage? Anything else?

Answer 1

• if q in dic is pointless. You initialized dic so that it does have all queries.
• dic = dict.fromkeys(queries, 0) should be a bit faster.
• dic is not a particularly meaningful name, counter or ctr would be better.
• Creating results at the start of the function gives the false impression that it's needed there already. I'd create it right before the loop that builds it. Then you'd have the complete counting part first, and the complete querying part afterwards. Or better yet, ...
• ... use a list comprehension, which is faster and nicer.
• Python already has a Counter class that does a lot for you and is probably faster.

from collections import Counter

def matchingStrings(strings, queries):
    ctr = Counter(strings)
    return [ctr[q] for q in queries]

For fun: 1000*1000 isn't super big, and HackerRank's calling code really only needs an iterable, so... this also gets accepted:

def matchingStrings(strings, queries):
    return map(strings.count, queries)

Answer 2

Any time you are using a dict, and you need to do something special the first time a key is used, take a look at collections.defaultdict().

from collections import defauldict

def matchingStrings(strings, queries):
    results = []

    counts = defaultdict(int)
    for s in strings:
        counts[s] += 1

    results = [counts[q] for q in queries]

    return results

Any time you need to count things, take a look at collections.Counter().

from collections import Counter

def matchingStrings(strings, queries):
    counts = Counter(strings)
    return [counts[q] for q in queries]