Untitled

class TrieNode {
    TrieNode[] children = new TrieNode[26]; // Chỉ hỗ trợ các ký tự 'a' đến 'z'
    boolean isEndOfWord;

    public TrieNode() {
        isEndOfWord = false;
    }
}

public class Trie {
    private final TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Thêm từ vào trie
    public void insert(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a'; // Tính vị trí của ký tự trong mảng
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }

    // Tìm kiếm từ trong trie
    public boolean search(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return current.isEndOfWord;
    }

    // Kiểm tra prefix
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return true;
    }

    // Xoá từ khỏi trie
    public boolean delete(String word) {
        return delete(root, word, 0);
    }

    private boolean delete(TrieNode current, String word, int index) {
        if (index == word.length()) {
            if (!current.isEndOfWord) {
                return false;
            }
            current.isEndOfWord = false;
            return isEmpty(current);
        }

        char c = word.charAt(index);
        int i = c - 'a';
        TrieNode node = current.children[i];
        if (node == null) {
            return false;
        }

        boolean shouldDeleteCurrentNode = delete(node, word, index + 1);

        if (shouldDeleteCurrentNode) {
            current.children[i] = null; // Xóa node hiện tại
            return isEmpty(current) && !current.isEndOfWord;
        }

        return false;
    }

    // Kiểm tra xem node có rỗng không (tức là không có node con)
    private boolean isEmpty(TrieNode node) {
        for (TrieNode child : node.children) {
            if (child != null) {
                return false;
            }
        }
        return true;
    }

    // Cập nhật từ trong trie (sửa từ)
    public void update(String oldWord, String newWord) {
        delete(oldWord);
        insert(newWord);
    }

    public static void main(String[] args) {
        Trie trie = new Trie();

        // Thêm từ
        trie.insert("hello");
        trie.insert("world");

        // Tìm kiếm từ
        System.out.println(trie.search("hello")); // true
        System.out.println(trie.search("hell"));  // false

        // Cập nhật từ
        trie.update("hello", "helloworld");
        System.out.println(trie.search("helloworld")); // true
        System.out.println(trie.search("hello"));      // false

        // Xoá từ
        trie.delete("world");
        System.out.println(trie.search("world")); // false
    }
}