How to implement a Trie data structures in Java?

A Trie, also known as a prefix tree, is a tree-like data structure that is used to store a dynamic set of strings. Tries are commonly used to perform efficient prefix searches, such as finding all words in a dictionary that begin with a particular prefix.

Here is an example of how you could implement a Trie in Java:

class TrieNode {
    private TrieNode[] children;
    private boolean isEnd;
 
    // Constructor
    public TrieNode() {
        children = new TrieNode[26];
        isEnd = false;
    }
 
    public TrieNode[] getChildren() {
        return children;
    }
 
    public boolean isEnd() {
        return isEnd;
    }
 
    public void setEnd(boolean end) {
        isEnd = end;
    }
}
 
class Trie {
    private TrieNode root;
 
    // Constructor
    public Trie() {
        root = new TrieNode();
    }
 
    // Inserts a word into the trie
    public void insert(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (current.getChildren()[index] == null) {
                current.getChildren()[index] = new TrieNode();
            }
            current = current.getChildren()[index];
        }
        current.setEnd(true);
    }
 
    // Returns if the word is in the trie
    public boolean search(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (current.getChildren()[index] == null) {
                return false;
            }
            current = current.getChildren()[index];
        }
        return current.isEnd();
    }
 
    // Returns if there is any word in the trie that starts with the given prefix
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (current.getChildren()[index] == null) {
                return false;
            }
            current = current.getChildren()[index];
        }
        return true;
    }
}

To use this Trie implementation, you can create a new Trie object and use the insert method to add words to the Trie. You can then use the search method to check if a word is in the Trie, and the startsWith method to check if there are any words in the Trie that start with a particular prefix.