I saw the following question online:

Init - Initlize data structure in O(1).

Insert(s) - Add string s to your Data Structure in O(|s|).

Remove(s) - Remove string s from your Data Structure in O(|s|).

PrefixExists(s) - return True if there exists 2 different strings s1,s2 (different from each other) such that s is a prefix of s1 and s1 is a prefix of s2 in O(|s|).

It's clear that I have to use TRIE but I'm not sure which data to save in each node and how to update it.

I though about saving a data which is equal to the sum of the data of children + how many $ signs children have ($ is the end of each string) while this worked for few strings I strongly believe it's wrong.

  • $\begingroup$ Storing an alphabetical letter in each "cell" should suffice. $\endgroup$
    – nir shahar
    Sep 12, 2021 at 10:46
  • $\begingroup$ @nirshahar can you elaborate? $\endgroup$
    – Dan
    Sep 12, 2021 at 10:58
  • $\begingroup$ Where online did you see this? Please credit the original source of all problems that you post here, and make sure to credit all copied material: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Nov 3, 2021 at 18:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.