Input1.txt

I ate dinner We had a three course meal Brad came to dinner with us He loves fish tacos In the end, we all felt like we ate too much We all agreed; it was a magnificent evening She is in a loveless relationship We have wall

puzzle1.txt

w o r l d a a d e f l b t d e l a d e r a b d e r

please write this task by using JAVA Language and https://algs4.cs.princeton.edu codes. u do not implement any library please

In this homework, you are expected to implement trie data structure and following functions. First of all, you should create a trie data structure, then you should insert all words in the given txt files, read from user. Finally, you should complete following functions: Boolean Search(String arg): This function should return true if given argument is in your trie, otherwise it should return false. Void autoComplete(String prefix): This function should print all strings start with given prefix in your trie, lexicographically. Void reverseAutoComplete(String suffix): This function should print all strings end with given suffix in your trie, lexicographically. For this function, you may consider using multi-trie solution, or research and use more complex data structures such as suffix arrays. 1 Void FullAutoComplete(String prefix, String suffix): This function should print all strings start with given prefix and end with given suffix in your trie, lexicographically. For this function, you may consider using multi-trie solution, or research and use more complex data structures such as suffix arrays. Void findTopK(int k): This function should print top k words that have most occurrences, lexicographically. For this function, you may use a symbol table that keeps track of the number of appearances of each key. Void SolvePuzzle(String filepath): This function should read input from the given filepath and print all possible words in your trie Example file,puzzlel.txt, is as follow: (Each character in the given .txt file is separated with one space character.) world aadet Ibtde lader abder You can move horizontally, vertically, and diagonally in the given grid. You should find and print all valid words in your trie such as "world", "water", "wall" etc, lexicographically. all valid words in your trie such as "world", "water", "wall" etc, lexicographically. Example inputs and outputs: Let input 1.txt has following lines: I ate dinner We had a three course meal Brad came to dinner with us He loves fish tacos In the end, we all felt like we ate too much We all agreed; it was a magnificent evening She is in a loveless relationship We have wall 1-) Search Input1.txt (enter words file) 1 (represents search function) (enter search word) Input1.txt (enter words file) (represents search function) (enter search word) 1 Ate had True True Input1.txt (enter words file) (represents search function) 1 1 Input1.txt (enter words file) (represents search function) money (enter search word) world (enter search word) False False 1-) Search Input1.txt (enter words file) 1 (represents search function) Input1.txt (enter words file) (represents search function) (enter search word) 1 Ate (enter search word) had True True Input1.txt (enter words file) Input1.txt (enter words file) 1 (represents search function) 1 (represents search function) (enter search word) world (enter search word) money False False 2-) AutoComplete Inputi.txt (enter words file) (represents autocomplete function) (enter auto-completed word) a, agreed, all, ate 2 Input1.txt (enter words file) (represents autocomplete function) (enter auto-completed word) lov loveless, loves Input1.txt (enter words file) 2 (represents autocomplete function) (enter auto-completed word) asds No words 3 3-) ReverseAutoComplete Input1.txt (enter words file) (represents reverse autocomplete function) (enter reverse auto-completed word) is, loveless, loves, tacos, us, was Input1.txt (enter words file) 3 (represents reverse autocomplete function) qx (enter reverse auto-completed word) No word 4-)FullComplete Input1.txt (enter words file) (represents full autocomplete function) thee (enter full auto-completed words, prefix and suffix respectively.) three Inputi.txt (enter words file) (represents full autocomplete function) (enter full auto-completed words, prefix and suffix respectively.) thc ee No word 5-) find TopK 5 Inputi.txt (enter words file) (represents find top k function) (enter number ) 2 a, we 6-) SolvePuzzle Input1.txt (enter words file) (represents solve puzzle function) puzzle 1.txt (enter puzzle file) a, all, ate, wall