search

emory-courses / dsa-java

Data Structures and Algorithms in Java
https://emory.gitbook.io/dsa-java/
42 stars 55 forks source link

[QZ#5] input #122

Closed caroltang0331 closed 3 years ago

caroltang0331 commented 3 years ago

Should we consider the input case containing one key that starts in the middle of another. For example, if "Czech Republic" and "Republic of Korea" are two valid keys in the trie, will we be given a input like, "I arrived at Czech Republic of Korea" I am just curious because I can't think of a real life example I had both implementation work but if we don't consider this possibility, I can skip some strings and do less comparison so might be slightly slightly faster.

marvinquiet commented 3 years ago

To my understanding, it is okay to have some non-sense input and extract out all possible entities out of it. Just make sure you describe your approach precisely and analyze the time-complexity.

lujiaying commented 3 years ago

The real-life application of Trie may contain the scenario you described. Imaging the stored keys are product names. It is possible that one long product name contains another name.