5.3. Quiz

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 class under the package that inherits by passing Integer as the generic type.

• Update the getEntities() method that takes an input string and returns the list of , 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.

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"