Suffix Trie Construction

Category: Tries

```

Problem Statement

• Creating the trie from a string; this will be done by calling the populateSuffixTrieFrom method upon class instantiation, which should populate the root of the class.
• Searching for strings in the trie. Note that every string added to the trie should end with the special endSymbol character: "" . If you're unfamiliar with Sux Tries, we recommend watching the Conceptual Overview section of this question's video explanation before starting to code. Sample Input (for creation) string = "babc" Sample Output (for creation) The structure below is the root of the trie. { "c": {"": true}, "b": { "c": {"": true}, "a": {"b": {"c": {"": true}}}, }, "a": {"b": {"c": {"": true}}}, } Sample Input (for searching in the sux trie above) string = "abc" Sample Output (for searching in the sux trie above) true Hints Hint 1 Building a sux-trie-like data structure consists of essentially storing every sux of a given string in a trie. To do so, iterate through the input string one character at a time and insert every substring starting at each character and ending at the end of the string into the trie. Hint 2 To insert a string into the trie, start by adding the rst character of the string into the root node of the trie and mapping it to an empty hash table if it isn't already there. Then, iterate through the rest of the string inserting each of the remaining characters into the previous character's corresponding node (or hash table) in the trie, making sure to add an endSymbol "" at the end. Hint 3 Searching the trie for a specic string should follow a nearly identical logic to the one used to add a string in the trie. Optimal Space & Time Complexity Creation: O(n^2) time | O(n^2) space - where n is the length of the input string Searching: O(m) time | O(1) space - where m is the length of the input string

```

Approach & Solution

Solution 1

```java import java.util.; class Program { static class TrieNode { Map children = new HashMap(); } static class SuffixTrie { TrieNode root = new TrieNode(); char endSymbol = ''; public SuffixTrie(String str) { populateSuffixTrieFrom(str); } // O(n^2) time | O(n^2) space public void populateSuffixTrieFrom(String str) { for (int i = 0; i < str.length(); i++) { insertSubstringStartingAt(i, str); } } public void insertSubstringStartingAt(int i, String str) { TrieNode node = root; for (int j = i; j < str.length(); j++) { char letter = str.charAt(j); if (!node.children.containsKey(letter)) { TrieNode newNode = new TrieNode(); node.children.put(letter, newNode); } node = node.children.get(letter); } node.children.put(endSymbol, null); } // O(m) time | O(1) space public boolean contains(String str) { TrieNode node = root; for (int i = 0; i < str.length(); i++) { char letter = str.charAt(i); if (!node.children.containsKey(letter)) { return false; } node = node.children.get(letter); } return node.children.containsKey(endSymbol); } } }

```

Test Cases

``` Test Case 1 { "string": "babc", "classMethodsToCall": [{"arguments": ["abc"], "method": "contains"}] } Test Case 2 { "string": "test", "classMethodsToCall": [ {"arguments": ["t"], "method": "contains"}, {"arguments": ["st"], "method": "contains"}, {"arguments": ["est"], "method": "contains"}, {"arguments": ["test"], "method": "contains"}, {"arguments": ["tes"], "method": "contains"} ] } Test Case 3 { "string": "invisible", "classMethodsToCall": [ {"arguments": ["e"], "method": "contains"}, {"arguments": ["le"], "method": "contains"}, {"arguments": ["ble"], "method": "contains"}, {"arguments": ["ible"], "method": "contains"}, {"arguments": ["sible"], "method": "contains"}, {"arguments": ["isible"], "method": "contains"}, {"arguments": ["visible"], "method": "contains"}, {"arguments": ["nvisible"], "method": "contains"}, {"arguments": ["invisible"], "method": "contains"}, {"arguments": ["nvisibl"], "method": "contains"} ] } Test Case 4 { "string": "1234556789", "classMethodsToCall": [ {"arguments": ["9"], "method": "contains"}, {"arguments": ["89"], "method": "contains"}, {"arguments": ["789"], "method": "contains"}, {"arguments": ["6789"], "method": "contains"}, {"arguments": ["56789"], "method": "contains"}, {"arguments": ["456789"], "method": "contains"}, {"arguments": ["3456789"], "method": "contains"}, {"arguments": ["23456789"], "method": "contains"}, {"arguments": ["123456789"], "method": "contains"}, {"arguments": ["45567"], "method": "contains"} ] } Test Case 5 { "string": "testtest", "classMethodsToCall": [ {"arguments": ["t"], "method": "contains"}, {"arguments": ["st"], "method": "contains"}, {"arguments": ["est"], "method": "contains"}, {"arguments": ["test"], "method": "contains"}, {"arguments": ["ttest"], "method": "contains"}, {"arguments": ["sttest"], "method": "contains"}, {"arguments": ["esttest"], "method": "contains"}, {"arguments": ["testtest"], "method": "contains"}, {"arguments": ["tt"], "method": "contains"} ] } Test Case 6 { "string": "ttttttttt", "classMethodsToCall": [ {"arguments": ["t"], "method": "contains"}, {"arguments": ["tt"], "method": "contains"}, {"arguments": ["ttt"], "method": "contains"}, {"arguments": ["tttt"], "method": "contains"}, {"arguments": ["ttttt"], "method": "contains"}, {"arguments": ["tttttt"], "method": "contains"}, {"arguments": ["ttttttt"], "method": "contains"}, {"arguments": ["tttttttt"], "method": "contains"}, {"arguments": ["ttttttttt"], "method": "contains"}, {"arguments": ["vvv"], "method": "contains"} ] }