Compartilhamento de tecnologia

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

原题链接🔗：Implementar Trie (árvore de prefixos)
dificuldade: Médio⭐️⭐️

tema

Trie (pronunciado como "tentar") ou árvore de prefixos É uma estrutura de dados em árvore usada para armazenar e recuperar chaves com eficiência em um conjunto de dados de string. Essa estrutura de dados tem alguns casos de uso, como preenchimento automático e verificação ortográfica.

Implemente a classe Trie:

• Trie() Inicialize o objeto da árvore de prefixos.
• void insert(String word) Inserir string na árvore de prefixosword 。
• boolean search(String word) se stringword Na árvore de prefixos, retorne true(ou seja, foi inserido antes da recuperação); caso contrário, retorna false 。
• boolean startsWith(String prefix) Se a string foi inserida antes wordUm dos prefixos é prefix ,retornar true ; Caso contrário, retornefalse。

Exemplo:

digitar
[“Trie”, “inserir”, “pesquisar”, “pesquisar”, “começa com”, “inserir”, “pesquisar”]
[[], [“maçã”], [“maçã”], [“aplicativo”], [“aplicativo”], [“aplicativo”], [“aplicativo”]]
saída
[nulo, nulo, verdadeiro, falso, verdadeiro, nulo, verdadeiro]

explicar
Trie trie = novo Trie();
trie.insert(“maçã”);
trie.search("apple"); // Retorna Verdadeiro
trie.search("app"); // Retorna Falso
trie.startsWith("app"); // Retorna Verdadeiro
trie.insert(“aplicativo”);
trie.search("app"); // Retorna Verdadeiro

dica:

• 1 <= comprimento.palavra, comprimento.prefixo <= 2000
• palavra e prefixo consistem apenas em letras minúsculas do inglês
• O número total de chamadas insert, search e startWith não excede 3 * 10⁴ Segunda categoria

árvore de prefixos

Uma árvore de prefixos, também conhecida como árvore Trie (pronuncia-se "try"), é uma estrutura de dados usada para armazenar coleções de strings, que permite recuperação e inserção rápida de strings, bem como consultas para prefixos de strings. Cada nó da árvore de prefixos representa um prefixo de uma string, e os filhos de cada nó representam todas as extensões possíveis do prefixo que adicionam um caractere.

• Características das árvores de prefixo：
  • eficiência de espaço: para coleções de strings com um grande número de prefixos comuns, as árvores de prefixos podem economizar espaço de armazenamento.
  • Eficiência de tempo: A complexidade de tempo das operações de inserção e pesquisa é geralmente O(m), onde m é o comprimento da string.
  • coleção dinâmica: a árvore de prefixos pode inserir e excluir strings dinamicamente, o que é adequado para cenários que exigem atualizações frequentes.
• Operações básicas de árvores de prefixo：
  • inserir: Insira uma string na árvore, começando no nó raiz e descendo caractere por caractere. Se o nó filho correspondente ao caractere não existir, crie um novo nó.
  • procurar: Pesquise se existe uma string na árvore, começando no nó raiz e descendo caractere por caractere. Se o nó filho de um caractere não existir, a pesquisa falhará.
  • Pesquisa de prefixo: Verifica se existe alguma string prefixada por uma determinada string, semelhante à operação de busca, mas não precisa verificar o flag final do último nó.
  • excluir: a exclusão de uma string de uma árvore requer a exclusão de nós recursivamente, garantindo ao mesmo tempo que os nós de prefixo comuns de outras strings não sejam excluídos.
• Cenários de aplicação da árvore de prefixos：
  • autocompletar: em mecanismos de busca ou editores de texto, fornece rapidamente sugestões de preenchimento com base nos prefixos inseridos pelo usuário.
  • Verificação ortográfica: verifica se a palavra digitada pelo usuário está escrita corretamente e fornece sugestões de ortografia corretas.
  • Roteamento IP: Em uma rede, a correspondência de prefixo mais longo é usada para determinar o caminho de roteamento de um pacote.
  • Análise de sequência genética: Em bioinformática, usado para combinar e recuperar rapidamente sequências genéticas.

responder

1. Ideias para resolução de problemas：

Um Trie (árvore de prefixo) é uma estrutura de dados em árvore usada para recuperação rápida de chaves em um conjunto de dados de string. É um tipo especial de árvore em que cada nó representa um caractere e o caminho da raiz até um nó representa uma string. As árvores Trie são frequentemente usadas para implementar funções como preenchimento automático e verificação ortográfica.

A seguir estão as etapas básicas e ideias de resolução de problemas para implementar uma árvore Trie:

1. Definir nós Trie：

   • Cada nó Trie geralmente contém um conjunto de caracteres ou um valor booleano para representar o final da palavra e ponteiros para nós filhos.

2. Inicializar teste：

   • Crie um nó raiz que não contenha caracteres, mas que sirva como ponto de partida para todas as palavras.

3. operação de inserção：

   • A partir do nó raiz, para cada caractere da string a ser inserido:
     • Se o nó filho correspondente ao personagem não existir, crie um novo nó filho.
     • Mova o nó atual para o nó filho correspondente.

4. Operação de pesquisa：

   • Começando no nó raiz, para cada caractere da string que você deseja pesquisar:
     • Se o nó filho correspondente ao caractere existir, continue a pesquisa.
     • Se não existir, uma falha de pesquisa será retornada.

5. Pesquisa de prefixo：

   • Semelhante à operação de pesquisa, mas só se preocupa se o prefixo da string existe.

6. Excluir operação(opcional):

   • Implemente a capacidade de excluir palavras conforme necessário, o que geralmente envolve a exclusão de nós e requer o tratamento da contagem de referências do nó.

7. Função de preenchimento automático(opcional):

   • Dado um prefixo, retorne todas as strings começando com esse prefixo.

2. demonstração 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

• Resultado de saída:

1
0
1

3. Endereço do armazém de código：Triste