Java에서 접두사 트리를 구현하는 방법

1. 접두사 트리

1. 접두사 트리란

사전 트리(Trie tree)는 문자열 저장 및 검색에 자주 사용되는 트리 형태의 데이터 구조입니다. 사전 트리의 핵심 아이디어는 문자열 사이에 공통 접두사를 사용하여 저장 공간을 절약하고 쿼리 효율성을 높이는 것입니다. 다중 트리이며 각 노드는 문자열의 접두사를 나타내며 루트 노드에서 리프 노드까지의 경로가 문자열을 구성합니다.

사전 트리의 루트 노드에는 문자가 포함되어 있지 않습니다. 각 하위 노드는 루트 노드에서 임의의 노드까지의 경로에 있는 문자가 해당 노드가 나타내는 문자열에 연결됩니다. 각 노드는 하나 이상의 문자열을 저장할 수 있으며 일반적으로 노드가 나타내는 문자열이 존재하는지 여부를 표시하는 플래그를 사용합니다. 문자열 집합에서 문자열을 찾아야 하는 경우 사전 트리를 사용하여 효율적인 검색 작업을 수행할 수 있습니다.

2. 접두사 트리의 예

예를 들어 문자열 배열 {"goog", "google", "bai", "baidu", "a"}에 대한 접두사 트리를 만듭니다. 접두사 보기 트리의 일부 특징:

• 루트 노드는 문자를 저장하지 않습니다.

• 접두사 트리는 다중 포크 트리입니다.

• 접두사 트리의 각 노드는 한 문자를 저장합니다.

• 같은 접두사를 가진 문자열은 같은 경로에 저장됨

• 문자열의 끝 부분에도 접두사 트리에 끝 기호가 있습니다.

2. 접두사 트리 구현

주제에 대한 208개의 질문 접두사 트리를 구현하는 것입니다:Likou

1. 접두사 트리의 데이터 구조

코드를 작성할 때 노드 정보를 저장하기 위해 해시 테이블을 사용하는 것을 선호합니다. 본질적으로 둘 다 배열을 사용할 수도 있습니다. 동일합니다

public class Trie {
    Map<Character, Trie> next;
    boolean isEnd;
    public Trie() {
        this.next = new HashMap<>();
        this.isEnd = false;
    }
    public void insert(String word) {
    }
    public boolean search(String word) {
        return false;
    }
    public boolean startsWith(String prefix) {
        return false;
    }
}

2. 문자열 삽입

    public void insert(String word) {
        Trie trie = this;//获得根结点
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null) {//当前结点不存在
                trie.next.put(c, new Trie());//创建当前结点
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        trie.isEnd = true;
    }

4. 접두사

    public boolean search(String word) {
        Trie trie = this;//获得根结点
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null) {//当前结点不存在
                return false;
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        return trie.isEnd;
    }

찾기 다음 단계는 단어 사전에서 가장 긴

에 대한 몇 가지 질문에 답하는 것입니다. 1. 질문 설명

문자열 배열

을 제공하고 점차적으로 사전에 있는 다른 단어에 한 글자를 추가합니다.

가능한 답변이 여러 개인 경우 답변 중 사전 편찬 순서가 가장 작은 단어가 반환됩니다. 대답이 없으면 빈 문자열이 반환됩니다.

words 组成的一本英语词典。返回words 中最长的一个单词，该单词是由wordsLiqun: Liqun

2. 문제 분석

이것은 일반적인 접두사 트리 질문이지만, 이 질문에는 몇 가지 특별한 요구 사항이 있습니다. 반환되는 답변은 다음과 같습니다.

1. 이 단어는 점차적으로 구성됩니다. 의 다른 단어

3. 동일한 길이는 더 작은 사전 순서를 반환합니다.

따라서 문자열을 하나씩 삽입하는 코드는 변경되지 않습니다. trie.next.get(c) == null에 있어야 하며 false로 판단하는 조건을 추가해야 합니다. 즉, 각 노드에는 각 노드에 단어가 있음을 나타내는 플래그가 있어야 합니다. 가장 긴 단어(리프 노드의 단어)를 형성합니다

3. 코드 구현

    public boolean startsWith(String prefix) {
        Trie trie = this;//获得根结点
        for (char c : prefix.toCharArray()) {
            if (trie.next.get(c) == null) {//当前结点不存在
                return false;
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        return true;
    }

위 내용은 Java에서 접두사 트리를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!