Code Optimization By Not Using Nested For Loop - Hackerrank Sparse Arrays-CodePudding

I need help.

My code / solution:

def matchingStrings(strings, queries):
    # Write your code here

    # strings = sorted(strings)
    # queries = sorted(queries)
    results = []

    LENGTH_Q = len(queries)
    LENGTH_S = len(strings)
    for i in range(LENGTH_Q):
        total = 0
        query = queries[i]
        for j in range(LENGTH_S):
            string = strings[j]
            if query == string:
                total  = 1
        results.append(total)

    return results

I believe my solution results to quadratic complexity which is not good. Please show me or give me hints on how to think of a better solution to this problem.

Thank you.

UPDATE:

I have a second version of my solution but still not sure if it is more efficient because I don't know how the function [LIST].count() works inside. Anyway, please take a look the 2nd version:

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

    LENGTH_Q = len(queries)
    for i in range(LENGTH_Q):
        query = queries[i]
        results.append(strings.count(query))

    return results

CodePudding user response：

Instead of getting the length of the queries list and using i as an index to reference each value, in python you could just do a for loop for the length of an iterable like this:

for query in queries:

Then instead of defining an empty list and appending counts in the for loop, you could use list comprehension like this:

results = [strings.count(query) for query in queries]

I've been watching Raymond Hettinger videos. He is the 'itertools guy'. He's also on stackoverflow.

In the video he also talks about generator expressions. If we take out the square brackets from the above maybe it uses less memory?

results = (strings.count(query) for query in queries)
return list(results)

I'm not sure if there are any good alternatives to .count() in this situation.