Chapter 9 prob: unique shortest prefix

#1

regarding chapter 9 prob (in version 1.2.1, this was 9.14) find the unique prefix, why are we using trie instead of just comparing strings one-by-one – because i believe the runtime is actually the same in either case?

more specifically, given this solution: https://github.com/epibook/epibook.github.io/blob/master/solutions/java/src/main/java/com/epi/ShortestUniquePrefix.java

why won’t we just straight up use String checkAns() method instead of doing trie-check?

now, only advantage i can see of solving w/ trie is if, you want to solve the same problem over and over again with the same set D, but with different string S each time (since trie is already created, so you can just plug-in different S’s and get the answer); however, given the problem statement (in version 1.2.1), we’re solving it just one time, so i don’t see any benefit of building and solving it w/ Trie

0 Likes
#2

ok, so i looked this prob up online since i thought i was missing something obvious; then i found ppl discussing the same problem here:

im basically agreeing w/ Barry here (2nd most voted answer). why won’t we just do this given the prob statement?

0 Likes
#3

Hey xjis,

First of all, thanks for asking this question, and you are right that trie is only useful as we query many times. We actually added one paragraph in the beginning of this solution in our recent revision as follows:

First, note that this problem only makes sense if the function is called many times with different query strings and an unchanging set of dictionary strings. Other- wise, there is nothing that can improve upon the brute-force approach of comparing the query string with each dictionary string.

In the future, we might change the problem description and make it like asking you to implement a service instead.

Thanks for your question, and please feel free to drop more of your questions to us.

0 Likes