Sparse Arrays| Array
TASK(medium)
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results.
Example
stringList=[‘ab’,’ab’,’abc’]
queries=[‘ab’,’abc’,’bc’]
There are 2 instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0] .
Function Description
Complete the function matchingStrings in the editor below. The function must return an array of integers representing the frequency of occurrence of each query string in stringList.
matchingStrings has the following parameters:
- string stringList[n] - an array of strings to search
- string queries[q] - an array of query strings
Returns
- int[q]: an array of results for each query
Input Format
The first line contains and integer n, the size of stringlist[].
Each of the next n lines contains a string stringlist[i].
The next line contains q, the size of queries[].
Each of the next q lines contains a string queries[i].
Constraints
1<n<1000
1<q<1000
1<|stringList[i]|<20
Sample Input 1
4
aba
baba
aba
xzxb
3
aba
xzxb
ab
Sample Output 1
2
1
0
Explanation 1
Here, "aba" occurs twice, in the first and third string. The string "xzxb" occurs once in the fourth string, and "ab" does not occur at all.
SOLUTION 1
def sparseArray(strings, queries):
# Create a dictionary to store the frequency of each string in the 'strings' list
frequency = {}
for string in strings:
if string in frequency:
frequency[string] += 1
else:
frequency[string] = 1
results = []
for query in queries:
results.append(frequency.get(query, 0))
return results
# Reading input
if __name__ == "__main__":
import sys
input = sys.stdin.read
data = input().splitlines()
# Read the number of strings
n = int(data[0])
# Read the strings
strings = [data[i+1] for i in range(n)]
# Read the number of queries
q = int(data[n+1])
# Read the queries
queries = [data[n+2+i] for i in range(q)]
# Get the result
result = sparseArray(strings, queries)
# Print the results, one per line
for count in result:
print(count)
SOLUTION 2
def sparseArray(strings, queries):
# Create a Counter to count the frequency of each string in the 'strings' list
frequency = Counter(strings)
# Prepare results for each query by fetching counts from the Counter
results = [frequency.get(query, 0) for query in queries]
return results
# Reading input
if __name__ == "__main__":
import sys
input = sys.stdin.read
data = input().splitlines()
# Read the number of strings
n = int(data[0])
# Read the strings
strings = [data[i+1] for i in range(n)]
# Read the number of queries
q = int(data[n+1])
queries = [data[n+2+i] for i in range(q)]
# Get the result
result = sparseArray(strings, queries)
for count in result:
print(count)
EXPLANATION STEPS
1. Function sparseArray(strings, queries):
- Uses a dictionary frequency to count the occurrences of each string in the strings list.
- For each query, retrieves the count from the dictionary using get(), which returns 0 if the query string is not found.
2. Handling Input and Output:
- Reads all input lines and parses them into the strings list and queries list.
- Calls sparseArray to compute the counts.
- Prints each count on a new line.
