5.3. Quiz

This section provides exercises for better understanding in tries.

Let L be a list of country names in String where spaces are allowed (e.g., "United States", "South Korea"). Consider a trie where all country names in L and their unique IDs are put as key-value pairs as follows:

Implementation

• Create the TrieQuiz class under the trie package that inherits Trie by passing Integer as the generic type.

• Update the getEntities() method that takes an input string and returns the list of Entity, where each entity consists of the begin index (inclusive) and end index (exclusive) of the first and the last characters of the corresponding country name respectively as well as the ID of the country name.

• See TrieQuizTest for an example of how to unit-test your approach.

Report

• Write a report that briefly describe your approach and explains the worst-case complexity of your approach, and save it as quiz5.pdf.

Notes

• Substring matching of country names is not required. If your dictionary has "United States" as a country name and the input string contains "United Nation", the "United" should not be matched as a country name.

• Substring matching within input words are expected. If your dictionary has "America" as a country name and the input contains "American", the first 7 characters, "America" should be recognized as a country name.

• The worst-case complexity needs to be explained in terms of the number of characters n in the input string.