artículo técnico

Un trie (pronunciado como "try") o árbol de prefijos es una estructura de datos de árbol utilizada para almacenar y recuperar claves de manera eficiente en un conjunto de datos de cadenas. Hay varias aplicaciones de esta estructura de datos, como el autocompletado y el corrector ortográfico.

Implementar la clase Trie:

Trie() Inicializa el objeto trie.
void insert(String word) Inserta la cadena palabra en el trie.
int countWordsEqualTo(String word) Devuelve la cantidad de instancias de la cadena word en el trie.
int countWordsStartingWith(String prefix) Devuelve la cantidad de cadenas en el trie que tienen el prefijo de cadena como prefijo.
void erase(String word) Borra la cadena palabra del trie.

Dada una cadena que contiene sólo los caracteres '(', ')', '{', '}', '[' y ']', determine si la cadena de entrada es válida.

Una cadena de entrada es válida si:

Los corchetes abiertos deben cerrarse con el mismo tipo de corchetes.
Los corchetes abiertos deben cerrarse en el orden correcto.
Cada corchete cerrado tiene un corchete abierto correspondiente del mismo tipo.

Dado un tablero mxn de caracteres y una lista de cadenas de palabras, devuelve todas las palabras del tablero.

Cada palabra debe construirse a partir de letras de celdas adyacentes secuencialmente, donde las celdas adyacentes están adyacentes horizontal o verticalmente. La misma celda de letra no puede usarse más de una vez en una palabra.

Diseñe una estructura de datos que admita agregar nuevas palabras y descubrir si una cadena coincide con alguna cadena agregada previamente.

Implementar la clase WordDictionary:

WordDictionary() Inicializa el objeto.
void addWord(word) Agrega palabra a la estructura de datos, puede coincidir más tarde.
bool search(word) Devuelve verdadero si hay alguna cadena en la estructura de datos que coincide con palabra o falso en caso contrario. La palabra puede contener puntos '.' donde los puntos se pueden combinar con cualquier letra.

Un trie (pronunciado como "try") o árbol de prefijos es una estructura de datos de árbol utilizada para almacenar y recuperar claves de manera eficiente en un conjunto de datos de cadenas. Hay varias aplicaciones de esta estructura de datos, como el autocompletado y el corrector ortográfico.

Implementar la clase Trie:

Trie() Inicializa el objeto trie.
void insert(String word) Inserta la cadena palabra en el trie.
boolean search(String word) Devuelve verdadero si la cadena palabra está en el trie (es decir, se insertó antes) y falso en caso contrario.
boolean startsWith(String prefix) Devuelve verdadero si hay una cadena palabra insertada previamente que tiene el prefijo prefix, y falso en caso contrario.

Dado un árbol de búsqueda binaria (BST), encuentre el nodo ancestro común más bajo (LCA) de dos nodos dados en el BST.

Según la definición de LCA en Wikipedia: “El ancestro común más bajo se define entre dos nodos p y q como el nodo más bajo en T que tiene tanto p como q como descendientes (donde permitimos que un nodo sea descendiente de sí mismo)”.

Dada la raíz de un árbol de búsqueda binario y un entero k, devuelve el késimo valor más pequeño (indexado a 1) de todos los valores de los nodos del árbol.

Dada la raíz de un árbol binario, determine si es un árbol de búsqueda binaria (BST) válido.

Una BST válida se define de la siguiente manera:

El subárbol izquierdo de un nodo contiene sólo nodos con claves menores que la clave del nodo.
El subárbol derecho de un nodo contiene sólo nodos con claves mayores que la clave del nodo.
Los subárboles izquierdo y derecho también deben ser árboles de búsqueda binarios.