Trie 구현(접두사 트리)

요구사항 정의

트리 ("try"로 발음) 또는 접두사 트리는 문자열 데이터세트에서 키를 효율적으로 저장하고 검색하는 데 사용되는 트리 데이터 구조입니다 . 자동 완성 및 맞춤법 검사기와 같은 이 데이터 구조의 다양한 응용 프로그램이 있습니다.

Trie 클래스를 구현합니다.

Trie()trie 개체를 초기화합니다.
void insert(String word)문자열을 word트라이에 삽입합니다.
boolean search(String word)true문자열이 word트라이에 있는지(즉, 이전에 삽입되었는지) 반환하고 , false그렇지 않으면 반환합니다.
boolean startsWith(String prefix)접두사가 있는 true이전에 삽입된 문자열이 있으면 반환 하고 그렇지 않으면 반환합니다 .wordprefixfalse

요구사항

Trie()trie 개체를 초기화합니다.

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

void insert(String word)문자열을 word트라이에 삽입합니다.

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;
}

boolean search(String word)true문자열이 word트라이에 있는지(즉, 이전에 삽입되었는지) 반환하고 , false그렇지 않으면 반환합니다.

public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }

boolean startsWith(String prefix)접두사가 있는 true이전에 삽입된 문자열이 있으면 반환 하고 그렇지 않으면 반환합니다 .wordprefixfalse

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

풀이생각

class TrieNode {
    TrieNode[] children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new TrieNode[26]; // Assuming lowercase English letters
        isEndOfWord = false;
    }
}

public 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 boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }

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