Contando el número de palabras en un Trie

Un Trie se utiliza para almacenar palabras del diccionario para que se puedan buscar de manera eficiente y se pueda realizar una búsqueda de prefijos. La tarea es escribir una función para contar el número de palabras. Ejemplo :

Input :     root
          /   \    \
         t   a     b
         |   |     |
         h   n     y
         |   |  \  |
         e   s  y  e
         /  |   |
         i  r   w
         |  |   |
         r  e   e
                |
                r
Output : 8
Explanation : Words formed in the Trie : 
"the", "a", "there", "answer", "any", "by", 
"bye", "their".

En la estructura Trie, tenemos un campo para almacenar el marcador de fin de palabra, lo llamamos isLeaf en la implementación a continuación. Para contar palabras, necesitamos simplemente atravesar el Trie y contar todos los Nodes donde está configurado isLeaf. 

Implementación:

C++

// C++ implementation to count words in a trie
#include <bits/stdc++.h>
using namespace std;
  
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
  
// Alphabet size (# of symbols)
#define ALPHABET_SIZE (26)
  
// Converts key current character into index
// use only 'a' through 'z' and lower case
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
 
// Trie node
struct TrieNode
{
    struct TrieNode *children[ALPHABET_SIZE];
  
    // isLeaf is true if the node represents
    // end of a word
    bool isLeaf;
};
  
// Returns new trie node (initialized to NULLs)
struct TrieNode *getNode(void)
{
    struct TrieNode *pNode = new TrieNode;
        pNode->isLeaf = false;
  
    for (int i = 0; i < ALPHABET_SIZE; i++)
        pNode->children[i] = NULL;   
  
    return pNode;
}
  
// If not present, inserts key into trie
// If the key is prefix of trie node, just
// marks leaf node
void insert(struct TrieNode *root, const char *key)
{
    int length = strlen(key);
 
    struct TrieNode *pCrawl = root;
  
    for (int level = 0; level < length; level++)
    {
        int index = CHAR_TO_INDEX(key[level]);
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
  
        pCrawl = pCrawl->children[index];
    }
  
    // mark last node as leaf
    pCrawl->isLeaf = true;
}
 
// Function to count number of words
int wordCount(struct TrieNode *root)
{
    int result = 0;
 
    // Leaf denotes end of a word
    if (root -> isLeaf)
        result++;
     
    for (int i = 0; i < ALPHABET_SIZE; i++)   
      if (root -> children[i])
         result += wordCount(root -> children[i]);
    
    return result;  
}
 
// Driver
int main()
{
    // Input keys (use only 'a' through 'z'
    // and lower case)
    char keys[][8] = {"the", "a", "there", "answer",
                     "any", "by", "bye", "their"};
 
  
    struct TrieNode *root = getNode();
  
    // Construct Trie
    for (int i = 0; i < ARRAY_SIZE(keys); i++)
        insert(root, keys[i]);
 
    cout << wordCount(root);
     
    return 0;
}

Java

// Java implementation to count words in a trie
public class Words_in_trie {
     
    // Alphabet size (# of symbols)
    static final int ALPHABET_SIZE = 26;
      
    // Trie node
    static class TrieNode
    {
        TrieNode[] children =  new TrieNode[ALPHABET_SIZE];
        // isLeaf is true if the node represents
        // end of a word
        boolean isLeaf;
         
        TrieNode(){
            isLeaf = false;
            for (int i = 0; i < ALPHABET_SIZE; i++)
                 children[i] = null;
        }
    };
    static TrieNode root;
       
    // If not present, inserts key into trie
    // If the key is prefix of trie node, just
    // marks leaf node
    static void insert(String key)
    {
        int length = key.length();
      
        TrieNode pCrawl = root;
       
        for (int level = 0; level < length; level++)
        {
            int index = key.charAt(level) - 'a';
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
       
            pCrawl = pCrawl.children[index];
        }
       
        // mark last node as leaf
        pCrawl.isLeaf = true;
    }
      
    // Function to count number of words
    static int wordCount(TrieNode root)
    {
        int result = 0;
      
        // Leaf denotes end of a word
        if (root.isLeaf)
            result++;
          
        for (int i = 0; i < ALPHABET_SIZE; i++)   
          if (root.children[i] != null )
             result += wordCount(root.children[i]);
         
        return result;  
    }
      
    // Driver Program
    public static void main(String args[])
    {
        // Input keys (use only 'a' through 'z'
        // and lower case)
        String keys[] = {"the", "a", "there", "answer",
                        "any", "by", "bye", "their"};
 
        root = new TrieNode();     
         
        // Construct Trie
        for (int i = 0; i < keys.length; i++)
            insert(keys[i]);
      
        System.out.println(wordCount(root));
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python implementation to count words in a trie
     
# Alphabet size (# of symbols)
from pickle import NONE
 
ALPHABET_SIZE = 26
 
# Trie node
class TrieNode:
         
    def __init__(self):
        # isLeaf is true if the node represents
        # end of a word
        self.isLeaf = False
        self.children = [None for i in range(ALPHABET_SIZE)]
     
 
root = TrieNode()
         
# If not present, inserts key into trie
# If the key is prefix of trie node, just
# marks leaf node
def insert(key):
 
    length = len(key)
     
    pCrawl = root
     
    for level in range(length):
 
        index = ord(key[level]) - ord('a')
        if (pCrawl.children[index] == None):
            pCrawl.children[index] = TrieNode()
         
        pCrawl = pCrawl.children[index]
         
    # mark last node as leaf
    pCrawl.isLeaf = True
 
     
# Function to count number of words
def wordCount(root):
 
    result = 0
     
    # Leaf denotes end of a word
    if (root.isLeaf == True):
        result += 1
         
    for i in range(ALPHABET_SIZE):   
        if (root.children[i] != None):
            result += wordCount(root.children[i])
         
    return result
     
# Driver Program
 
# Input keys (use only 'a' through 'z'
# and lower case)
keys = ["the", "a", "there", "answer", "any", "by", "bye", "their"];
 
root = TrieNode()
 
# Construct Trie
for i in range(len(keys)):
    insert(keys[i])
     
print(wordCount(root))
 
# This code is contributed by shinjanpatra

C#

// C# implementation to count words in a trie
using System;
 
public class Words_in_trie
{
     
    // Alphabet size (# of symbols)
    static readonly int ALPHABET_SIZE = 26;
     
    // Trie node
    public class TrieNode
    {
        public TrieNode[] children = new TrieNode[ALPHABET_SIZE];
         
        // isLeaf is true if the node represents
        // end of a word
        public bool isLeaf;
         
        public TrieNode()
        {
            isLeaf = false;
            for (int i = 0; i < ALPHABET_SIZE; i++)
                children[i] = null;
        }
    };
    static TrieNode root;
         
    // If not present, inserts key into trie
    // If the key is prefix of trie node, just
    // marks leaf node
    static void insert(String key)
    {
        int length = key.Length;
     
        TrieNode pCrawl = root;
         
        for (int level = 0; level < length; level++)
        {
            int index = key[level] - 'a';
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
         
            pCrawl = pCrawl.children[index];
        }
         
        // mark last node as leaf
        pCrawl.isLeaf = true;
    }
     
    // Function to count number of words
    static int wordCount(TrieNode root)
    {
        int result = 0;
     
        // Leaf denotes end of a word
        if (root.isLeaf)
            result++;
         
        for (int i = 0; i < ALPHABET_SIZE; i++)
        if (root.children[i] != null )
            result += wordCount(root.children[i]);
         
        return result;
    }
     
    // Driver code
    public static void Main()
    {
        // Input keys (use only 'a' through 'z'
        // and lower case)
        String []keys = {"the", "a", "there", "answer",
                        "any", "by", "bye", "their"};
 
        root = new TrieNode();
         
        // Construct Trie
        for (int i = 0; i < keys.Length; i++)
            insert(keys[i]);
     
        Console.WriteLine(wordCount(root));
    }
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
 
// JavaScript implementation to count words in a trie
     
// Alphabet size (# of symbols)
const ALPHABET_SIZE = 26;
 
// Trie node
class TrieNode
{
         
    constructor(){
        // isLeaf is true if the node represents
        // end of a word
        this.isLeaf = false;
        this.children = new Array(ALPHABET_SIZE).fill(null);
    }
}
 
let root = new TrieNode();
         
    // If not present, inserts key into trie
    // If the key is prefix of trie node, just
    // marks leaf node
function insert(key)
{
    let length = key.length;
     
    let pCrawl = root;
     
    for (let level = 0; level < length; level++)
    {
        let index = key.charCodeAt(level) - 'a'.charCodeAt(0);
        if (pCrawl.children[index] == null)
            pCrawl.children[index] = new TrieNode();
         
        pCrawl = pCrawl.children[index];
    }
         
    // mark last node as leaf
    pCrawl.isLeaf = true;
}
     
// Function to count number of words
function wordCount(root)
{
    let result = 0;
     
    // Leaf denotes end of a word
    if (root.isLeaf)
        result++;
         
    for (let i = 0; i < ALPHABET_SIZE; i++)   
        if (root.children[i] != null )
            result += wordCount(root.children[i]);
         
    return result;
}
     
// Driver Program
 
// Input keys (use only 'a' through 'z'
// and lower case)
let keys = ["the", "a", "there", "answer", "any", "by", "bye", "their"];
 
root = new TrieNode();   
 
// Construct Trie
for (let i = 0; i < keys.length; i++)
    insert(keys[i]);
     
document.write(wordCount(root),"</br>");
 
// This code is contributed by shinjanpatra
 
</script>
Producción

8

Este artículo es una contribución de Rohit Thapliyal . 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.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *