Doubt in Treasure Hunt Problem

#1

Couldn’t understand how to approach the problem.

Can u pls explain the approach to the problem and the intuition behind the approach ??

#2

I think this can be done with the help of a map with strings as keys or with tries …
since implementing with map is easy i will explain u that.

  1. Iterate over the array
  2. For every ith string … just traverse it and for every prefix of it . Just search it in the map if it is already present. If not insert it else just increment the value of map[prefix] ++.
  3. If the count of a certain prefix is suppose x then the total combinations would be x*(x+1)/2. simple xC2 combinatorics.
  4. That’s it now just traverse the map and check for every key its length and the value that it holds i.e the x that is explained above.
#3

but this approach will run in O(N*N), won’t it ? And we’ve to find an O(N) approach ! So i think tries should be used

#4

No it will run in O(N*max(string.size))…so that’s fine since we do need to traverse in the strings otherwise how will we check the prefixes

#5

but how will this approach take into account LCPs of len = 0 ?? I tried the approach but it is giving wa on sample tc

#6

my sol : https://ide.codingblocks.com/s/292628

#7

and i think my implementation isn’t working as reqd, can u pls tell where my implementation is going wrong ?

#8

Hi sorry for the late reply… I couldn’t find error in ur code. Can u please ask this to ur mentor?