rahul_bhaiya_sabka_baap's blog

How to solve this problem?
By rahul_bhaiya_sabka_baap, history, 6 years ago, In English

You have a dictionary with set of words, you have to create a data structure which will give you no of words of length L whose ith character is C. Queries are very frequent, Try to optimize it. If possible, please do provide the code.

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it can be solved offline. convert the query for length exactly L in two modified queries of length <=L and <=L-1. Now queries of <=L can be solved offline, sort the words in increasing order of length. Maintain an arr[][26] where arr[i][c] denotes the number of words we've seen that have ith character as c. Initially all values in arr are 0. Using two pointers, iterate on both queries and the words, updating the arr as you go. In the end, for each original query, find the two modified queries, and subtract their answers, and print original queries in the asked order.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My bad, there's quite an easy solution as well, that can do it online. Maintain 26 vectors, each for a-z. Iterate on all strings and push the vectors (i,length_of_string) in the ith character's vector. Sort all vectors first by i and then by l, now all queries can be easily answered using binary search.

→ Reply