Package Struct
Class Trie
java.lang.Object
Struct.Trie
A Trie (or Prefix Tree) data structure implementation that supports efficient
insertion and search operations for strings. It optimizes space and time complexities
where several strings have common prefixes.
- Since:
- 1.0
- Version:
- 1.0
- Author:
- Sahasrad Chippa
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionboolean
contains
(CharSequence word) Checks if a word is in the Trie.void
insert
(CharSequence word) Inserts a word into the Trie.
-
Constructor Details
-
Trie
public Trie()Constructs an empty Trie with default lowercase alphabet settings (a-z). -
Trie
public Trie(char[] allowedChars) Constructs a Trie specifying allowed characters. It customizes the structure to optimize for the provided set of characters.- Parameters:
allowedChars
- The array of allowed characters to include in the Trie.
-
Trie
Constructs a Trie specifying allowed characters. It customizes the structure to optimize for the provided set of characters, intended for situations where allowed characters are contained within a list.- Parameters:
allowedChars
- The list of allowed characters to include in the Trie.
-
-
Method Details
-
insert
Inserts a word into the Trie. If any character in the word is out of the allowed range, it throws an exception. Runs inO(m)
where m is the length of the word.- Parameters:
word
- A sequence of characters representing the word to insert.- Throws:
IllegalArgumentException
- If an invalid character is in the input String.
-
contains
Checks if a word is in the Trie. Runs inO(m)
where m is the length of the word.- Parameters:
word
- The word to check.- Returns:
- true if the Trie contains the word, false otherwise.
-