사전 트리(Trie tree)는 문자열 저장 및 검색에 자주 사용되는 트리 형태의 데이터 구조입니다. 사전 트리의 핵심 아이디어는 문자열 사이에 공통 접두사를 사용하여 저장 공간을 절약하고 쿼리 효율성을 높이는 것입니다. 다중 트리이며 각 노드는 문자열의 접두사를 나타내며 루트 노드에서 리프 노드까지의 경로가 문자열을 구성합니다.
사전 트리의 루트 노드에는 문자가 포함되어 있지 않습니다. 각 하위 노드는 루트 노드에서 임의의 노드까지의 경로에 있는 문자가 해당 노드가 나타내는 문자열에 연결됩니다. 각 노드는 하나 이상의 문자열을 저장할 수 있으며 일반적으로 노드가 나타내는 문자열이 존재하는지 여부를 표시하는 플래그를 사용합니다. 문자열 집합에서 문자열을 찾아야 하는 경우 사전 트리를 사용하여 효율적인 검색 작업을 수행할 수 있습니다.
예를 들어 문자열 배열 {"goog", "google", "bai", "baidu", "a"}에 대한 접두사 트리를 만듭니다. 접두사 보기 트리의 일부 특징:
루트 노드는 문자를 저장하지 않습니다.
접두사 트리는 다중 포크 트리입니다.
접두사 트리의 각 노드는 한 문자를 저장합니다.
같은 접두사를 가진 문자열은 같은 경로에 저장됨
문자열의 끝 부분에도 접두사 트리에 끝 기호가 있습니다.
주제에 대한 208개의 질문 접두사 트리를 구현하는 것입니다:Likou
코드를 작성할 때 노드 정보를 저장하기 위해 해시 테이블을 사용하는 것을 선호합니다. 본질적으로 둘 다 배열을 사용할 수도 있습니다. 동일합니다
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; } }
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; }
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
中最长的一个单词,该单词是由words
Liqun: Liqun
2. 문제 분석
이것은 일반적인 접두사 트리 질문이지만, 이 질문에는 몇 가지 특별한 요구 사항이 있습니다. 반환되는 답변은 다음과 같습니다.
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!