Cuente la cantidad de palabras con el prefijo dado usando Trie

Prerrequisito: Trie 

Dada una lista de strings str[] y una string de prefijos pre . La tarea es contar el número de palabras en la lista de strings con el prefijo dado usando trie .

Ejemplos: 

Entrada: str = [ “apk”, “app”, “apple”, “arp”, “array” ], pre = “ap” 
Salida: 3 
Explicación: 
A continuación se muestra la representación de trie usando la string anterior. 
 

Las palabras en str que tienen el prefijo «ap» son apk , app y apple . 
entonces la cuenta es 3

Entrada: str = [ “gee”, “geek”, “geezer”, “geeksforgeeks”, “geekiness”, “geekgod” ], pre = “geek” 
Salida: 4 

Enfoque: 
para resolver este problema , se utiliza la estructura de datos Trie y cada Node de este Trie contiene los siguientes tres campos:  

1. children : este campo se usa para mapear desde un personaje al siguiente nivel de trie node
2. isEndOfWord : este campo se utiliza para distinguir el Node como Node de fin de palabra
3. num : este campo se utiliza para contar el número de veces que se visita un Node durante la inserción en trie

Pasos: 

• Inserte una lista de strings en trie de modo que cada string en la lista se inserte como un Node trie individual.
• Durante la inserción, actualice todos los campos en cada Node del trie
• Para un prefijo dado, atraviese el trie hasta llegar al último carácter del prefijo dado pre .
• El valor del campo numérico en el último Node de la string pre es el recuento de prefijos en la lista de strings dada.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of counting the
// number of words in a trie with a
// given prefix
#include "bits/stdc++.h"
using namespace std;
 
// Trie Node
struct TrieNode {
 
    // Using map to store the pointers
    // of children nodes for dynamic
    // implementation, for making the
    // program space efficient
    map<char, TrieNode*> children;
 
    // If isEndOfWord is true, then
    // node represents end of word
    bool isEndOfWord;
 
    // num represents number of times
    // a character has appeared during
    // insertion of the words in the
    // trie
    map<char, int> num;
};
 
// Declare root node
struct TrieNode* root;
 
// Function to create New Trie Node
struct TrieNode* getNewTrieNode()
{
    struct TrieNode* pNode = new TrieNode;
    pNode->isEndOfWord = false;
    return pNode;
}
 
// Function to insert a string in trie
void insertWord(string word)
{
    // To hold the value of root
    struct TrieNode* current = root;
 
    // To hold letters of the word
    char s;
 
    // Traverse through strings in list
    for (int i = 0; i < word.length(); i++) {
        s = word[i];
 
        // If s is not present in the
        // character field of current node
        if (current->children.find(s)
            == current->children.end()) {
 
            // Get new node
            struct TrieNode* p = getNewTrieNode();
 
            // Insert s in character
            // field of current node
            // with reference to node p
            (current->children)[s] = p;
 
            // Insert s in num field
            // of current node with
            // value 1
            (current->num)[s] = 1;
        }
        else {
 
            // Increment the count
            // corresponding to the
            // character s
            current->num[s] = (current->num)[s] + 1;
        }
 
        // Go to next node
        current = (current->children)[s];
    }
    current->isEndOfWord = true;
}
 
// Function to count the number of
// words in trie with given prefix
int countWords(vector<string>& words,
               string prefix)
{
    root = getNewTrieNode();
 
    // Size of list of string
    int n = words.size();
 
    // Construct trie containing
    // all the words
    for (int i = 0; i < n; i++) {
        insertWord(words[i]);
    }
 
    struct TrieNode* current = root;
    char s;
 
    // Initialize the wordCount = 0
    int wordCount = 0;
 
    for (int i = 0; prefix[i]; i++) {
        s = prefix[i];
 
        // If the complete prefix is
        // not present in the trie
        if (current->children.find(s)
            == current->children.end()) {
 
            // Make wordCount 0 and
            // break out of loop
            wordCount = 0;
            break;
        }
 
        // Update the wordCount
        wordCount = (current->num)[s];
 
        // Go to next node
        current = (current->children)[s];
    }
 
    return wordCount;
}
 
// Driver Code
int main()
{
    // input list of words
    vector<string> words;
    words = { "apk", "app", "apple",
              "arp", "array" };
 
    // Given prefix to find
    string prefix = "ap";
 
    // Print the number of words with
    // given prefix
    cout << countWords(words, prefix);
    return 0;
}

# Python3 implementation of counting the
# number of words in a trie with a
# given prefix
  
# Trie Node
class TrieNode:
     
    def __init__(self):
         
        # Using map to store the pointers
        # of children nodes for dynamic
        # implementation, for making the
        # program space efficient
        self.children = dict()
     
        # If isEndOfWord is true, then
        # node represents end of word
        self.isEndOfWord = False
     
        # num represents number of times
        # a character has appeared during
        # insertion of the words in the
        # trie
        self.num = dict()
 
# Declare root node
root = None
 
# Function to create New Trie Node
def getNewTrieNode():
     
    pNode = TrieNode()
    return pNode
  
# Function to insert a string in trie
def insertWord(word):
     
    global root
     
    # To hold the value of root
    current = root
  
    # To hold letters of the word
    s = ''
  
    # Traverse through strings in list
    for i in range(len(word)):
        s = word[i]
  
        # If s is not present in the
        # character field of current node
        if (s not in current.children):
  
            # Get new node
            p = getNewTrieNode()
             
            # Insert s in character
            # field of current node
            # with reference to node p
            current.children[s] = p
  
            # Insert s in num field
            # of current node with
            # value 1
            current.num[s] = 1
        else:
  
            # Increment the count
            # corresponding to the
            # character s
            current.num[s] = current.num[s] + 1
  
        # Go to next node
        current = current.children[s]
     
    current.isEndOfWord = True
 
# Function to count the number of
# words in trie with given prefix
def countWords(words, prefix):
     
    global root
    root = getNewTrieNode()
  
    # Size of list of string
    n = len(words)
  
    # Construct trie containing
    # all the words
    for i in range(n):
        insertWord(words[i])
         
    current = root
    s = ''
  
    # Initialize the wordCount = 0
    wordCount = 0
     
    for i in range(len(prefix)):
        s = prefix[i]
  
        # If the complete prefix is
        # not present in the trie
        if (s not in current.children):
  
            # Make wordCount 0 and
            # break out of loop
            wordCount = 0
            break
         
        # Update the wordCount
        wordCount = (current.num)[s]
  
        # Go to next node
        current = (current.children)[s]
  
    return wordCount
 
# Driver Code
if __name__=='__main__':
     
    # input list of words
    words = [ "apk", "app", "apple",
              "arp", "array" ]
  
    # Given prefix to find
    prefix = "ap"
  
    # Print the number of words with
    # given prefix
    print(countWords(words, prefix))
     
# This code is contributed by rutvik_56

3

Complejidad de tiempo: O(n*l) donde n = número de palabras insertadas en Trie y l = longitud de la palabra más larga insertada en Trie.