Compartir tecnología

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

原题链接🔗：Implementar Trie (árbol de prefijos)
dificultad: Medio⭐️⭐️

tema

Trie (pronunciado como "intentar") o árbol de prefijos Es una estructura de datos de árbol que se utiliza para almacenar y recuperar claves de manera eficiente en un conjunto de datos de cadenas. Esta estructura de datos tiene bastantes casos de uso, como el autocompletado y la revisión ortográfica.

Implemente la clase Trie:

• Trie() Inicialice el objeto del árbol de prefijos.
• void insert(String word) Insertar cadena en el árbol de prefijosword 。
• boolean search(String word) si cadenaword En el árbol de prefijos, regrese true(es decir, se ha insertado antes de la recuperación); de lo contrario, devuelve); false 。
• boolean startsWith(String prefix) Si la cadena se ha insertado antes wordUno de los prefijos es prefix ,devolver true ; De lo contrario, regresefalse。

Ejemplo:

ingresar
[“Trie”, “insertar”, “buscar”, “buscar”, “startsWith”, “insertar”, “buscar”]
[[], [“manzana”], [“manzana”], [“aplicación”], [“aplicación”], [“aplicación”], [“aplicación”]]
producción
[nulo, nulo, verdadero, falso, verdadero, nulo, verdadero]

explicar
Trie trie = nuevo Trie();
trie.insert(“manzana”);
trie.search("manzana"); // Devuelve verdadero
trie.search("aplicación"); // Devuelve Falso
trie.startsWith("aplicación"); // Devuelve Verdadero
trie.insert(“aplicación”);
trie.search("aplicación"); // Devuelve Verdadero

pista:

• 1 <= longitud de palabra, longitud de prefijo <= 2000
• La palabra y el prefijo constan únicamente de letras minúsculas en inglés.
• El número total de llamadas de inserción, búsqueda e inicios con no supera 3 * 10⁴ De segunda categoría

árbol de prefijos

Un árbol de prefijos, también conocido como árbol Trie (pronunciado "try"), es una estructura de datos utilizada para almacenar colecciones de cadenas, lo que permite una rápida recuperación e inserción de cadenas, así como consultas de prefijos de cadenas. Cada nodo del árbol de prefijos representa un prefijo de una cadena y los hijos de cada nodo representan todas las extensiones posibles del prefijo que agregan un carácter.

• Características de los árboles de prefijos：
  • eficiencia espacial: Para colecciones de cadenas con una gran cantidad de prefijos comunes, los árboles de prefijos pueden ahorrar espacio de almacenamiento.
  • eficiencia de tiempo: La complejidad temporal de las operaciones de inserción y búsqueda suele ser O (m), donde m es la longitud de la cadena.
  • colección dinámica: El árbol de prefijos puede insertar y eliminar cadenas dinámicamente, lo cual es adecuado para escenarios que requieren actualizaciones frecuentes.
• Operaciones básicas de árboles de prefijos.：
  • insertar: Inserte una cadena en el árbol, comenzando desde el nodo raíz y bajando carácter por carácter. Si el nodo secundario correspondiente al carácter no existe, cree un nuevo nodo.
  • buscar: busca si existe una cadena en el árbol, comenzando desde el nodo raíz y bajando carácter por carácter. Si el nodo secundario de un carácter no existe, la búsqueda falla.
  • Búsqueda de prefijo: Comprueba si hay alguna cadena con el prefijo de una determinada cadena, similar a la operación de búsqueda, pero no necesita verificar el indicador de fin del último nodo.
  • borrar: Eliminar una cadena de un árbol requiere eliminar nodos de forma recursiva y al mismo tiempo garantizar que no se eliminen los nodos de prefijo comunes de otras cadenas.
• Escenarios de aplicación del árbol de prefijos：
  • Autocompletar: En motores de búsqueda o editores de texto, proporcione rápidamente sugerencias de finalización basadas en los prefijos ingresados ​​por el usuario.
  • Corrector ortográfico: Comprueba si la palabra ingresada por el usuario está escrita correctamente y proporciona sugerencias ortográficas correctas.
  • enrutamiento IP: En una red, la coincidencia de prefijo más larga se utiliza para determinar la ruta de enrutamiento de un paquete.
  • Análisis de secuencia genética.: En bioinformática, se utiliza para unir y recuperar rápidamente secuencias de genes.

respuesta

1. Ideas para resolver problemas：

Un Trie (árbol de prefijos) es una estructura de datos de árbol que se utiliza para la recuperación rápida de claves en un conjunto de datos de cadenas. Es un tipo especial de árbol en el que cada nodo representa un carácter y la ruta desde la raíz hasta un nodo representa una cadena. Los árboles Trie se utilizan a menudo para implementar funciones como la finalización automática y la revisión ortográfica.

Los siguientes son los pasos básicos y las ideas de resolución de problemas para implementar un árbol Trie:

1. Definir nodos Trie：

   • Cada nodo Trie normalmente contiene un conjunto de caracteres o un valor booleano para representar el final de la palabra y punteros a nodos secundarios.

2. Inicializar intento：

   • Cree un nodo raíz que no contenga caracteres pero que sirva como punto de partida para todas las palabras.

3. operación de inserción：

   • Comenzando desde el nodo raíz, para cada carácter de la cadena que se insertará:
     • Si el nodo secundario correspondiente al personaje no existe, cree un nuevo nodo secundario.
     • Mueva el nodo actual al nodo secundario correspondiente.

4. Operación de búsqueda：

   • Comenzando desde el nodo raíz, para cada carácter de la cadena que desea buscar:
     • Si el nodo secundario correspondiente al personaje existe, continúe buscando.
     • Si no existe, se devuelve un error de búsqueda.

5. Búsqueda de prefijo：

   • Similar a la operación de búsqueda, pero solo le importa si existe el prefijo de la cadena.

6. Eliminar operación(opcional):

   • Implemente la capacidad de eliminar palabras según sea necesario, lo que generalmente implica eliminar nodos y requiere manejar el recuento de referencias del nodo.

7. Función de autocompletar(opcional):

   • Dado un prefijo, devuelve todas las cadenas que comienzan con ese prefijo.

2. demostración de 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 salida:

1
0
1

3. Dirección del almacén de códigos：Intentar