기술나눔

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

原题链接🔗：Trie 구현(접두사 트리)
어려움: 중간⭐️⭐️

주제

Trie("시도"처럼 발음) 또는 접두사 트리 문자열 데이터세트에서 키를 효율적으로 저장하고 검색하는 데 사용되는 트리 데이터 구조입니다. 이 데이터 구조에는 자동 완성 및 맞춤법 검사와 같은 꽤 많은 사용 사례가 있습니다.

Trie 클래스를 구현하십시오.

• Trie() 접두사 트리 개체를 초기화합니다.
• void insert(String word) 접두사 트리에 문자열 삽입word 。
• boolean search(String word) 문자열이면word 접두사 트리에서 반환 true(즉, 검색 전에 삽입되었습니다), 그렇지 않으면 반환됩니다. false 。
• boolean startsWith(String prefix) 문자열이 이전에 삽입된 경우 word접두사 중 하나는 다음과 같습니다. prefix ,반품 true ; 그렇지 않으면 반환false。

예:

입력하다
[“Trie”, “삽입”, “검색”, “검색”, “startsWith”, “삽입”, “검색”]
[[], [“애플”], [“애플”], [“앱”], [“앱”], [“앱”], [“앱”]]
산출
[null,null,true,false,true,null,true]

설명하다
트라이 트라이 = 새로운 트라이();
trie.insert("사과");
trie.search("apple"); // True를 반환합니다.
trie.search("app"); // 거짓 반환
trie.startsWith("app"); // True를 반환합니다.
trie.insert("앱");
trie.search("app"); // True를 반환합니다.

힌트:

• 1 <= 단어 길이, 접두사 길이 <= 2000
• 단어와 접두사는 영문 소문자로만 구성됩니다.
• 삽입, 검색 및 startWith 호출의 총 개수는 3 * 10을 초과하지 않습니다.⁴ 이류

접두사 트리

Trie 트리("try"로 발음)라고도 알려진 접두사 트리는 문자열 모음을 저장하는 데 사용되는 데이터 구조로, 문자열 접두사에 대한 쿼리뿐만 아니라 문자열의 빠른 검색 및 삽입을 허용합니다. 접두사 트리의 각 노드는 문자열의 접두사를 나타내고, 각 노드의 자식은 한 문자를 추가하는 접두사의 가능한 모든 확장을 나타냅니다.

• 접두사 트리의 특성：
  • 공간 효율성: 공통 접두사가 많은 문자열 모음의 경우 접두사 트리를 사용하면 저장 공간을 절약할 수 있습니다.
  • 시간 효율성: 삽입 및 검색 작업의 시간 복잡도는 일반적으로 O(m)입니다. 여기서 m은 문자열의 길이입니다.
  • 동적 컬렉션: 접두사 트리는 문자열을 동적으로 삽입하고 삭제할 수 있으므로 자주 업데이트해야 하는 시나리오에 적합합니다.
• 접두사 트리의 기본 작업：
  • 끼워 넣다: 루트 노드부터 한 문자씩 아래로 내려가는 문자열을 트리에 삽입합니다. 해당 문자에 해당하는 하위 노드가 없으면 새 노드를 만듭니다.
  • 찾다: 루트 노드부터 한 문자씩 아래로 트리에 문자열이 있는지 검색합니다. 해당 문자의 하위 노드가 없으면 검색이 실패합니다.
  • 접두사 검색: 검색 작업과 유사하게 특정 문자열이 앞에 붙은 문자열이 있는지 확인하지만 마지막 노드의 종료 플래그를 확인할 필요는 없습니다.
  • 삭제: 트리에서 문자열을 삭제하려면 다른 문자열의 공통 접두사 노드가 삭제되지 않도록 하면서 노드를 재귀적으로 삭제해야 합니다.
• 접두사 트리의 응용 시나리오：
  • 자동완성: 검색 엔진이나 텍스트 편집기에서 사용자가 입력한 접두사를 기반으로 신속하게 완성 제안을 제공합니다.
  • 맞춤법 검사: 사용자가 입력한 단어의 철자가 올바른지 확인하고 올바른 철자를 제안합니다.
  • IP 라우팅: 네트워크에서는 가장 긴 접두사 일치를 사용하여 패킷의 라우팅 경로를 결정합니다.
  • 유전자 서열 분석: 생물정보학에서 유전자 서열을 신속하게 일치시키고 검색하는 데 사용됩니다.

답변

1. 문제 해결 아이디어：

Trie(접두사 트리)는 문자열 데이터세트에서 키를 빠르게 검색하는 데 사용되는 트리 데이터 구조입니다. 각 노드가 문자를 나타내고 루트에서 노드까지의 경로가 문자열을 나타내는 특별한 종류의 트리입니다. 트라이 트리는 자동 완성, 맞춤법 검사 등의 기능을 구현하는 데 자주 사용됩니다.

다음은 Trie 트리 구현을 위한 기본 단계와 문제 해결 아이디어입니다.

1. Trie 노드 정의：

   • 각 Trie 노드에는 일반적으로 단어의 끝을 나타내는 문자 집합이나 부울 값과 하위 노드에 대한 포인터가 포함되어 있습니다.

2. 트라이 초기화：

   • 문자는 포함하지 않지만 모든 단어의 시작점 역할을 하는 루트 노드를 만듭니다.

3. 삽입 작업：

   • 루트 노드부터 시작하여 삽입할 문자열의 각 문자에 대해 다음을 수행합니다.
     • 해당 캐릭터에 해당하는 자식 노드가 존재하지 않는 경우, 새로운 자식 노드를 생성합니다.
     • 현재 노드를 해당 하위 노드로 이동합니다.

4. 검색작업：

   • 루트 노드부터 시작하여 검색하려는 문자열의 각 문자에 대해 다음을 수행합니다.
     • 해당 캐릭터에 해당하는 자식 노드가 존재하면 검색을 계속합니다.
     • 존재하지 않으면 검색 실패가 반환됩니다.

5. 접두사 검색：

   • 검색 작업과 유사하지만 문자열의 접두사가 존재하는지 여부에만 관심이 있습니다.

6. 삭제 작업(선택 과목):

   • 필요에 따라 단어를 삭제하는 기능을 구현합니다. 여기에는 일반적으로 노드 삭제가 포함되며 노드의 참조 카운트 처리가 필요합니다.

7. 자동완성 기능(선택 과목):

   • 접두사가 주어지면 해당 접두사로 시작하는 모든 문자열을 반환합니다.

2. c++ 데모：

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};


int main() {
    Trie trie;
    trie.insert("apple");
    std::cout << trie.search("apple") << std::endl;   // 返回 1
    std::cout << trie.search("app") << std::endl;     // 返回 0
    std::cout << trie.startsWith("app") << std::endl; // 返回 1

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

• 출력 결과:

1
0
1

3. 코드 창고 주소：트리