We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
If you wanna read more to know my solution then continue.
Honestly, the task is really simple if you think about it carefully. You will need to find the first instance that will make a bad set, none found then it will be a good set. As the order matter and you need the first instance (hence, no sorting should be done), you should approach it will linear approach, or in simple words, go from the beginning to the end. When you examine an instance, you need to think: will it make a bad set (and return immediately) or not; and there are 2 cases can happen: it is the prefix of the previous ones or one of the previous ones is the prefix of it. So the key here is to store the previous ones so the later can check. And it hit me, HASHTABLE, 2 HASHTABLES, one for storing the prefixes (break a word into prefixes) and one just store the previous words. And you only need to check the hashtables and update them on your go. Voila, done! Technically speaking, this is O(n) because accessing the HTs is O(1) and you can argue that the loop over each string is O(1) as well as each string at max is 60 (kinda why this algo works haha).
No Prefix Set
You are viewing a single comment's thread. Return to all comments →
Don't overcomplicate it!
Hint: use 2 hashtables (HT)
If you wanna read more to know my solution then continue.
Honestly, the task is really simple if you think about it carefully. You will need to find the first instance that will make a bad set, none found then it will be a good set. As the order matter and you need the first instance (hence, no sorting should be done), you should approach it will linear approach, or in simple words, go from the beginning to the end. When you examine an instance, you need to think: will it make a bad set (and return immediately) or not; and there are 2 cases can happen: it is the prefix of the previous ones or one of the previous ones is the prefix of it. So the key here is to store the previous ones so the later can check. And it hit me, HASHTABLE, 2 HASHTABLES, one for storing the prefixes (break a word into prefixes) and one just store the previous words. And you only need to check the hashtables and update them on your go. Voila, done! Technically speaking, this is O(n) because accessing the HTs is O(1) and you can argue that the loop over each string is O(1) as well as each string at max is 60 (kinda why this algo works haha).
Below would be the solution in Python