You are viewing a single comment's thread. Return to all comments →
Your solution runs in O(n*q). It is possible to do O(n+q). Here is a faster algorithm.
Create a HashMap<String,Integer>
for each string in the first set
if the map contains the string increment the associated int
else put it in the map associated with 1
for each string in the second set
if the map contains the string print the associated int
else print 0
I believe this also could be implemented in two lines of code, but that's not my style. I used 7, thought it easier to read.
Best you can do with map-based is O((n+q)*logN). Think about HashMap performance when all strings have same hashcodes, your solution is O(n*q) as well. Only in java8 they introduced "treemap inside hashmap" for equi-hash comparable objects.
Here is reference to a 3-liner for hashmap solution in java8, maybe you'll like it