Dada una array de palabras, encuentre todos los prefijos únicos más cortos para representar cada palabra en la array dada. Supongamos que ninguna palabra es prefijo de otra.
Ejemplos:
Input: arr[] = {"zebra", "dog", "duck", "dove"}
Output: dog, dov, du, z
Explanation: dog => dog
dove => dov
duck => du
zebra => z
Input: arr[] = {"geeksgeeks", "geeksquiz", "geeksforgeeks"};
Output: geeksf, geeksg, geeksq}
Una solución simple es considerar cada prefijo de cada palabra (comenzando desde el más corto hasta el más grande), y si un prefijo no es prefijo de ninguna otra string, entonces imprímalo.
Una solución eficiente es usar Trie . La idea es mantener un conteo en cada Node. A continuación se muestran los pasos.
1) Construya un Trie de todas las palabras. También mantenga la frecuencia de cada Node (aquí la frecuencia es la cantidad de veces que se visita el Node durante la inserción). La complejidad temporal de este paso es O(N) donde N es el número total de caracteres en todas las palabras.
2) Ahora, para cada palabra, encontramos el carácter más cercano a la raíz con una frecuencia de 1. El prefijo de la palabra es la ruta desde la raíz hasta este carácter. Para hacer esto, podemos atravesar Trie comenzando desde la raíz. Para cada Node que se atraviesa, comprobamos su frecuencia. Si la frecuencia es uno, imprimimos todos los caracteres desde la raíz hasta este Node y no recorremos este Node.
Complejidad de tiempo si este paso también es O(N) donde N es el número total de caracteres en todas las palabras.
root
/ \
(d, 3)/ \(z, 1)
/ \
Node1 Node2
/ \ \
(o,2)/ \(u,1) \(e,1)
/ \ \
Node1.1 Node1.2 Node2.1
/ \ \ \
(g,1)/ \ (t,1) \(c,1) \(b,1)
/ \ \ \
Leaf Leaf Node1.2.1 Node2.1.1
(dog) (dot) \ \
\(k, 1) \(r, 1)
\ \
Leaf Node2.1.1.1
(duck) \
\(a,1)
\
Leaf
(zebra)
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to print all prefixes that
// uniquely represent words.
#include<bits/stdc++.h>
using namespace std;
#define MAX 256
// Maximum length of an input word
#define MAX_WORD_LEN 500
// Trie Node.
struct trieNode
{
struct trieNode *child[MAX];
int freq; // To store frequency
};
// Function to create a new trie node.
struct trieNode *newTrieNode(void)
{
struct trieNode *newNode = new trieNode;
newNode->freq = 1;
for (int i = 0; i<MAX; i++)
newNode->child[i] = NULL;
return newNode;
}
// Method to insert a new string into Trie
void insert(struct trieNode *root, string str)
{
// Length of the URL
int len = str.length();
struct trieNode *pCrawl = root;
// Traversing over the length of given str.
for (int level = 0; level<len; level++)
{
// Get index of child node from current character
// in str.
int index = str[level];
// Create a new child if not exist already
if (!pCrawl->child[index])
pCrawl->child[index] = newTrieNode();
else
(pCrawl->child[index]->freq)++;
// Move to the child
pCrawl = pCrawl->child[index];
}
}
// This function prints unique prefix for every word stored
// in Trie. Prefixes one by one are stored in prefix[].
// 'ind' is current index of prefix[]
void findPrefixesUtil(struct trieNode *root, char prefix[],
int ind)
{
// Corner case
if (root == NULL)
return;
// Base case
if (root->freq == 1)
{
prefix[ind] = '\0';
cout << prefix << " ";
return;
}
for (int i=0; i<MAX; i++)
{
if (root->child[i] != NULL)
{
prefix[ind] = i;
findPrefixesUtil(root->child[i], prefix, ind+1);
}
}
}
// Function to print all prefixes that uniquely
// represent all words in arr[0..n-1]
void findPrefixes(string arr[], int n)
{
// Construct a Trie of all words
struct trieNode *root = newTrieNode();
root->freq = 0;
for (int i = 0; i<n; i++)
insert(root, arr[i]);
// Create an array to store all prefixes
char prefix[MAX_WORD_LEN];
// Print all prefixes using Trie Traversal
findPrefixesUtil(root, prefix, 0);
}
// Driver function.
int main()
{
string arr[] = {"zebra", "dog", "duck", "dove"};
int n = sizeof(arr)/sizeof(arr[0]);
findPrefixes(arr, n);
return 0;
}
Java
// Java program to print all prefixes that
// uniquely represent words.
public class Unique_Prefix_Trie {
static final int MAX = 256;
// Maximum length of an input word
static final int MAX_WORD_LEN = 500;
// Trie Node.
static class TrieNode
{
TrieNode[] child = new TrieNode[MAX];
int freq; // To store frequency
TrieNode() {
freq =1;
for (int i = 0; i < MAX; i++)
child[i] = null;
}
}
static TrieNode root;
// Method to insert a new string into Trie
static void insert(String str)
{
// Length of the URL
int len = str.length();
TrieNode pCrawl = root;
// Traversing over the length of given str.
for (int level = 0; level<len; level++)
{
// Get index of child node from current character
// in str.
int index = str.charAt(level);
// Create a new child if not exist already
if (pCrawl.child[index] == null)
pCrawl.child[index] = new TrieNode();
else
(pCrawl.child[index].freq)++;
// Move to the child
pCrawl = pCrawl.child[index];
}
}
// This function prints unique prefix for every word stored
// in Trie. Prefixes one by one are stored in prefix[].
// 'ind' is current index of prefix[]
static void findPrefixesUtil(TrieNode root, char[] prefix,
int ind)
{
// Corner case
if (root == null)
return;
// Base case
if (root.freq == 1)
{
prefix[ind] = '\0';
int i = 0;
while(prefix[i] != '\0')
System.out.print(prefix[i++]);
System.out.print(" ");
return;
}
for (int i=0; i<MAX; i++)
{
if (root.child[i] != null)
{
prefix[ind] = (char) i;
findPrefixesUtil(root.child[i], prefix, ind+1);
}
}
}
// Function to print all prefixes that uniquely
// represent all words in arr[0..n-1]
static void findPrefixes(String arr[], int n)
{
// Construct a Trie of all words
root = new TrieNode();
root.freq = 0;
for (int i = 0; i<n; i++)
insert(arr[i]);
// Create an array to store all prefixes
char[] prefix = new char[MAX_WORD_LEN];
// Print all prefixes using Trie Traversal
findPrefixesUtil(root, prefix, 0);
}
// Driver function.
public static void main(String args[])
{
String arr[] = {"zebra", "dog", "duck", "dove"};
int n = arr.length;
findPrefixes(arr, n);
}
}
// This code is contributed by Sumit Ghosh
C#
// C# program to print all prefixes that
// uniquely represent words.
using System;
public class Unique_Prefix_Trie
{
static readonly int MAX = 256;
// Maximum length of an input word
static readonly int MAX_WORD_LEN = 500;
// Trie Node.
public class TrieNode
{
public TrieNode[] child = new TrieNode[MAX];
public int freq; // To store frequency
public TrieNode()
{
freq = 1;
for (int i = 0; i < MAX; i++)
child[i] = null;
}
}
static TrieNode root;
// Method to insert a new string into Trie
static void insert(String str)
{
// Length of the URL
int len = str.Length;
TrieNode pCrawl = root;
// Traversing over the length of given str.
for (int level = 0; level<len; level++)
{
// Get index of child node from
// current character in str.
int index = str[level];
// Create a new child if not exist already
if (pCrawl.child[index] == null)
pCrawl.child[index] = new TrieNode();
else
(pCrawl.child[index].freq)++;
// Move to the child
pCrawl = pCrawl.child[index];
}
}
// This function prints unique prefix for every word stored
// in Trie. Prefixes one by one are stored in prefix[].
// 'ind' is current index of prefix[]
static void findPrefixesUtil(TrieNode root, char[] prefix,
int ind)
{
// Corner case
if (root == null)
return;
// Base case
if (root.freq == 1)
{
prefix[ind] = '\0';
int i = 0;
while(prefix[i] != '\0')
Console.Write(prefix[i++]);
Console.Write(" ");
return;
}
for (int i = 0; i < MAX; i++)
{
if (root.child[i] != null)
{
prefix[ind] = (char) i;
findPrefixesUtil(root.child[i], prefix, ind + 1);
}
}
}
// Function to print all prefixes that uniquely
// represent all words in arr[0..n-1]
static void findPrefixes(String []arr, int n)
{
// Construct a Trie of all words
root = new TrieNode();
root.freq = 0;
for (int i = 0; i < n; i++)
insert(arr[i]);
// Create an array to store all prefixes
char[] prefix = new char[MAX_WORD_LEN];
// Print all prefixes using Trie Traversal
findPrefixesUtil(root, prefix, 0);
}
// Driver code
public static void Main()
{
String []arr = {"zebra", "dog", "duck", "dove"};
int n = arr.Length;
findPrefixes(arr, n);
}
}
/* This code contributed by PrinciRaj1992 */
Producción:
dog dov du z
Gracias a Gaurav Ahirwar por sugerir la solución anterior.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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