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.