Untitled

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord;
    int index = -1;

    public TrieNode() {
        isEndOfWord = false;
    }
}

public class Trie {
    private TrieNode root;
    private int currentIndex = 0;
    private int size = 0; // Biến đếm số lượng từ trong trie
    private Random random = new Random(); // Đối tượng Random để chọn chỉ số ngẫu nhiên

    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];
        }
        if (!current.isEndOfWord) {
            current.isEndOfWord = true;
            current.index = currentIndex++;
            size++; // Tăng biến đếm nếu từ này là từ mới
        }
    }

    // Hàm lấy chỉ số bất kỳ của từ chứa tiền tố truyền vào
    public int getRandomIndexOfPrefix(String prefix) {
        TrieNode current = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return -1; // Tiền tố không tồn tại
            }
            current = current.children[index];
        }

        // Lấy danh sách tất cả chỉ số từ hoàn chỉnh bắt đầu với tiền tố
        List<Integer> indices = new ArrayList<>();
        findAllWordIndices(current, indices);

        // Nếu không có từ nào chứa tiền tố, trả về -1
        if (indices.isEmpty()) {
            return -1;
        }

        // Chọn ngẫu nhiên một chỉ số từ danh sách
        int randomIndex = random.nextInt(indices.size());
        return indices.get(randomIndex);
    }

    // Hàm tìm tất cả chỉ số từ hoàn chỉnh bắt đầu từ node hiện tại
    private void findAllWordIndices(TrieNode node, List<Integer> indices) {
        if (node.isEndOfWord) {
            indices.add(node.index); // Thêm chỉ số của từ hoàn chỉnh vào danh sách
        }

        // Duyệt qua các node con để tìm tất cả các từ hoàn chỉnh
        for (TrieNode child : node.children) {
            if (child != null) {
                findAllWordIndices(child, indices);
            }
        }
    }

    // Hàm lấy từ dựa trên chỉ số truyền vào
    public String getWordByIndex(int targetIndex) {
        StringBuilder word = new StringBuilder();
        return findWordByIndex(root, targetIndex, word) ? word.toString() : null;
    }

    // Đệ quy duyệt qua các node để tìm từ với chỉ số yêu cầu
    private boolean findWordByIndex(TrieNode node, int targetIndex, StringBuilder word) {
        if (node.isEndOfWord && node.index == targetIndex) {
            return true; // Tìm thấy từ có chỉ số bằng với targetIndex
        }

        // Duyệt qua tất cả các node con và tìm từ hoàn chỉnh
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                char c = (char) (i + 'a');
                word.append(c); // Thêm ký tự vào từ
                if (findWordByIndex(node.children[i], targetIndex, word)) {
                    return true; // Nếu tìm thấy từ với chỉ số yêu cầu, trả về true
                }
                word.deleteCharAt(word.length() - 1); // Loại bỏ ký tự khi quay lại
            }
        }

        return false;
    }

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

        // Thêm từ
        trie.insert("hello");
        trie.insert("hell");
        trie.insert("helmet");
        trie.insert("help");
        trie.insert("hero");
        trie.insert("world");

        // Lấy chỉ số ngẫu nhiên của từ chứa tiền tố "hel"
        System.out.println("Random index of prefix 'hel': " + trie.getRandomIndexOfPrefix("hel"));
        System.out.println("Random index of prefix 'he': " + trie.getRandomIndexOfPrefix("he"));
        System.out.println("Random index of prefix 'wor': " + trie.getRandomIndexOfPrefix("wor"));
        System.out.println("Random index of prefix 'abc': " + trie.getRandomIndexOfPrefix("abc")); // Không tồn tại

        // Lấy từ dựa trên chỉ số
        System.out.println("Word at index 0: " + trie.getWordByIndex(0)); // "hello"
        System.out.println("Word at index 1: " + trie.getWordByIndex(1)); // "hell"
        System.out.println("Word at index 4: " + trie.getWordByIndex(4)); // "hero"
    }
}