Trie, also known as a prefix tree, is a tree-like data structure that stores strings by sharing common prefixes among them. This design optimizes space usage when handling sets of strings with overlapping beginnings.

For instance, strings "abc" and "abd" share the prefix "ab," allowing a single path for "ab" with diverging branches for 'c' and 'd'. Inserting "abf" extends this path, while adding "bc" creates a separate branch due to no shared prefix. To mark complete strings within the tree, nodes representing word ending are flagged—enabling detection of substrings like "ab" within longer entries.

Applications include search autocomplete systems, where typing triggesr suggestions based on prefixes, and sensitive word filtering. For filtering, a trie is built from banned terms. Consider filtering "abcdefghi" against sensitive words "de," "bca," and "bcf." A trie is constructed from these words:

root
├─ d ─ e (end)
└─ b ─ c ─ a (end)
          ─ f (end)

Traversal uses pointers: p1 tracks the current trie node (starting at root), p2 scans the input string, and p3 marks the start of a potential match. The algorithm proceeds character by character:

• If p1 has a child matching p2's character, advance p1 and p2.
• If no match exists, reset p1 to root and move p3 and p2 forward.
• When p1 reaches an end-marked node, the substring from p3 to p2 is a sansitive word, replaced with asterisks.

Complexity analysis: Building the trie for t sensitive words of average length m takes O(t * m). Filtering a string of length n involves O(n * m) time in worst-case scenarios, though prefix sharing often reduces this. The trie is reusable once constructed.

Implementation in Java uses hash maps for dynamic child node management, providing O(1) access. Below is a revised code example with restructured logic and renamed variables.

class TrieNode {
    private boolean terminal = false;
    private Map<Character, TrieNode> children = new HashMap<>();

    public void insertChild(char ch, TrieNode node) {
        children.put(ch, node);
    }

    public TrieNode fetchChild(char ch) {
        return children.get(ch);
    }

    public void markTerminal(boolean status) {
        terminal = status;
    }

    public boolean isTerminal() {
        return terminal;
    }
}

class TrieFilter {
    private TrieNode root = new TrieNode();
    private static final String MASK = "*";

    private boolean isSpecialChar(char ch) {
        int code = (int) ch;
        return !Character.isLetterOrDigit(ch) && (code < 0x2E80 || code > 0x9FFF);
    }

    public void insertTerm(String word) {
        if (word == null || word.isEmpty()) return;
        TrieNode current = root;
        for (int idx = 0; idx < word.length(); idx++) {
            char letter = word.charAt(idx);
            if (isSpecialChar(letter)) continue;
            TrieNode next = current.fetchChild(letter);
            if (next == null) {
                next = new TrieNode();
                current.insertChild(letter, next);
            }
            current = next;
            if (idx == word.length() - 1) current.markTerminal(true);
        }
    }

    public String censorText(String input) {
        if (input == null || input.trim().isEmpty()) return input;
        StringBuilder output = new StringBuilder();
        TrieNode current = root;
        int start = 0, scan = 0;
        while (scan < input.length()) {
            char ch = input.charAt(scan);
            if (isSpecialChar(ch)) {
                if (current == root) {
                    output.append(ch);
                    start++;
                }
                scan++;
                continue;
            }
            current = current.fetchChild(ch);
            if (current == null) {
                output.append(input.charAt(start));
                scan = start + 1;
                start = scan;
                current = root;
            } else if (current.isTerminal()) {
                output.append(MASK);
                scan++;
                start = scan;
                current = root;
            } else {
                scan++;
            }
        }
        output.append(input.substring(start));
        return output.toString();
    }
}

class Demo {
    public static void main(String[] args) {
        TrieFilter filter = new TrieFilter();
        filter.insertTerm("de");
        filter.insertTerm("bca");
        filter.insertTerm("bcf");
        String result = filter.censorText("abcdefghi");
        System.out.println(result); // Output: abc*fghi
    }
}