Die Anzahl der Wörter in einem Trie zählen
Ein Trie wird verwendet, um Wörterbuchwörter zu speichern, damit sie effizient durchsucht werden können und eine Präfixsuche durchgeführt werden kann. Die Aufgabe besteht darin, eine Funktion zu schreiben, um die Anzahl der Wörter zu zählen.
Beispiel :
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".
In der Trie-Struktur haben wir ein Feld zum Speichern der Wortende-Markierung, wir nennen es isLeaf in der folgenden Implementierung. Um Wörter zu zählen, müssen wir einfach den Trie durchlaufen und alle Node zählen, auf denen isLeaf gesetzt ist.
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
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 */
8
Dieser Artikel wurde von Rohit Thapliyal beigesteuert . Wenn Ihnen GeeksforGeeks gefällt und Sie etwas beitragen möchten, können Sie auch einen Artikel über Contribute.geeksforgeeks.org schreiben schreiben oder Ihren Artikel per E-Mail an Contribute@geeksforgeeks.org senden. Sehen Sie, wie Ihr Artikel auf der Hauptseite von GeeksforGeeks erscheint, und helfen Sie anderen Geeks.
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .