[JAVA]Trie를 이용한 접두사 검색 (Autocomplete 기능 구현)

Trie를 이용한 접두사 검색 (Autocomplete 기능 구현)

 

import java.util.*;

class TrieNode {
    TrieNode[] children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new TrieNode[26]; // 알파벳 소문자 기준
        isEndOfWord = false;
    }
}

class Trie {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    public List<String> getWordsWithPrefix(String prefix) {
        List<String> result = new ArrayList<>();
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return result;
            }
            node = node.children[index];
        }
        findWords(node, new StringBuilder(prefix), result);
        return result;
    }

    private void findWords(TrieNode node, StringBuilder prefix, List<String> result) {
        if (node.isEndOfWord) {
            result.add(prefix.toString());
        }
        for (char c = 'a'; c <= 'z'; c++) {
            int index = c - 'a';
            if (node.children[index] != null) {
                prefix.append(c);
                findWords(node.children[index], prefix, result);
                prefix.deleteCharAt(prefix.length() - 1);
            }
        }
    }
}