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