Coincidencia de prefijos en Python usando el módulo pytrie

Dada una lista de strings y una substring de valor de prefijo, ¿buscar todas las strings de la lista de strings dada que contiene el valor dado como prefijo? Ejemplos:

Input : arr = ['geeksforgeeks', 'forgeeks', 
               'geeks', 'eeksfor'], 
       prefix = 'geek'
Output : ['geeksforgeeks','geeks']

Un enfoque simple para resolver este problema es recorrer la lista completa y hacer coincidir el prefijo dado con cada string una por una, imprimir todas las strings que contienen el valor dado como prefijo. Tenemos una solución existente para resolver este problema utilizando Trie Data Structure . Podemos implementar Trie en python usando el módulo pytrie.StringTrie() .

Crear, insertar, buscar y eliminar en pytrie.StringTrie() ?

• Crear: trie=pytrie.StringTrie() crea una estructura de datos trie vacía.
• Insertar: trie[key]=value , key son los datos que queremos insertar en trie y value es similar al depósito que se agrega justo después del último Node de la clave insertada y este depósito contiene el valor real de la clave insertada.
• Buscar: trie.values(prefix) , devuelve la lista de todas las claves que contienen el prefijo dado.
• Eliminar: del trie[key] , elimina la clave especificada de la estructura de datos trie.

Nota: para instalar el paquete pytrie , use este comando pip install pytrie –user desde la terminal en Linux

# Function which returns all strings
# that contains given prefix
from pytrie import StringTrie
 
def prefixSearch(arr,prefix):
     
    # create empty trie
    trie=StringTrie()
 
    # traverse through list of strings
    # to insert it in trie. Here value of
    # key is itself key because at last
    # we need to return
    for key in arr:
        trie[key] = key
 
    # values(search) method returns list
    # of values of keys which contains
    # search pattern as prefix
    return trie.values(prefix)
 
# Driver program
if __name__ == "__main__":
    arr = ['geeksforgeeks','forgeeks','geeks','eeksfor']
    prefix = 'geek'
    output = prefixSearch(arr,prefix)
    if len(output) > 0:
        print (output)
    else:
        print ('Pattern not found')

Producción:

['geeksforgeeks','geeks']

Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.