Untitled

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord;
    int index = -1; // Lưu chỉ số của từ nếu đây là từ cuối

    public TrieNode() {
        isEndOfWord = false;
    }
}

public class Trie {
    private final TrieNode root;
    private int currentIndex = 0; // Đếm chỉ số cho từ

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

    // Thêm từ vào trie và gán chỉ số cho từ đó
    public void insert(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
        if (current.index == -1) { // Chỉ gán chỉ số nếu từ này chưa có chỉ số
            current.index = currentIndex++;
        }
    }

    // Tìm kiếm từ và trả về chỉ số của từ nếu tìm thấy
    public int get(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return -1; // Từ không tồn tại
            }
            current = current.children[index];
        }
        return current.isEndOfWord ? current.index : -1;
    }

    // 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;
            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");
        trie.insert("hell");

        // Lấy chỉ số của từ
        System.out.println("Index of 'hello': " + trie.get("hello")); // Index of 'hello': 0
        System.out.println("Index of 'world': " + trie.get("world")); // Index of 'world': 1
        System.out.println("Index of 'hell': " + trie.get("hell"));   // Index of 'hell': 2
        System.out.println("Index of 'unknown': " + trie.get("unknown")); // Index of 'unknown': -1

        // Cập nhật từ
        trie.update("hello", "helloworld");
        System.out.println("Index of 'helloworld': " + trie.get("helloworld")); // Index of 'helloworld': 3
        System.out.println("Index of 'hello': " + trie.get("hello"));           // Index of 'hello': -1

        // Xoá từ
        trie.delete("world");
        System.out.println("Index of 'world': " + trie.get("world")); // Index of 'world': -1
    }
}