Dado un diccionario de palabras donde cada palabra sigue la notación CamelCase, imprima todas las palabras en el diccionario que coincidan con un patrón dado que consiste solo en caracteres en mayúsculas.
CamelCase es la práctica de escribir palabras compuestas o frases de modo que cada palabra o abreviatura comience con una letra mayúscula. Los ejemplos comunes incluyen: «PowerPoint» y «WikiPedia», «GeeksForGeeks», «CodeBlocks», etc.
Ejemplos:
Input:
dict[] = ["Hi", "Hello", "HelloWorld", "HiTech", "HiGeek",
"HiTechWorld", "HiTechCity", "HiTechLab"]
For pattern "HT",
Output: ["HiTech", "HiTechWorld", "HiTechCity", "HiTechLab"]
For pattern "H",
Output: ["Hi", "Hello", "HelloWorld", "HiTech", "HiGeek",
"HiTechWorld", "HiTechCity", "HiTechLab"]
For pattern "HTC",
Output: ["HiTechCity"]
Input:
dict[] = ["WelcomeGeek","WelcomeToGeeksForGeeks", "GeeksForGeeks"]
For pattern "WTG",
Output: ["WelcomeToGeeksForGeeks"]
For pattern "GFG",
Output: [GeeksForGeeks]
For pattern "GG",
Output: No match found
La idea es insertar todas las claves del diccionario en el Trie una por una. Aquí la clave se refiere solo a caracteres en mayúsculas en la palabra original en notación CamelCase. Si encontramos la clave por primera vez, debemos marcar el último Node como Node hoja e insertar la palabra completa para esa clave en el vector asociado con el Node hoja. Si encontramos una clave que ya está en el trie, actualizamos el vector asociado con el Node hoja con la palabra actual. Después de procesar todas las palabras del diccionario, buscamos el patrón en el trie e imprimimos todas las palabras que coinciden con el patrón.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to print all words in the CamelCase
// dictionary that matches with a given pattern
#include <bits/stdc++.h>
using namespace std;
// Alphabet size (# of upper-Case characters)
#define ALPHABET_SIZE 26
// A Trie node
struct TrieNode
{
TrieNode* children[ALPHABET_SIZE];
// isLeaf is true if the node represents
// end of a word
bool isLeaf;
// vector to store list of complete words
// in leaf node
list<string> word;
};
// Returns new Trie node (initialized to NULLs)
TrieNode* getNewTrieNode(void)
{
TrieNode* pNode = new TrieNode;
if (pNode)
{
pNode->isLeaf = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
pNode->children[i] = NULL;
}
return pNode;
}
// Function to insert word into the Trie
void insert(TrieNode* root, string word)
{
int index;
TrieNode* pCrawl = root;
for (int level = 0; level < word.length(); level++)
{
// consider only uppercase characters
if (islower(word[level]))
continue;
// get current character position
index = int(word[level]) - 'A';
if (!pCrawl->children[index])
pCrawl->children[index] = getNewTrieNode();
pCrawl = pCrawl->children[index];
}
// mark last node as leaf
pCrawl->isLeaf = true;
// push word into vector associated with leaf node
(pCrawl->word).push_back(word);
}
// Function to print all children of Trie node root
void printAllWords(TrieNode* root)
{
// if current node is leaf
if (root->isLeaf)
{
for(string str : root->word)
cout << str << endl;
}
// recurse for all children of root node
for (int i = 0; i < ALPHABET_SIZE; i++)
{
TrieNode* child = root->children[i];
if (child)
printAllWords(child);
}
}
// search for pattern in Trie and print all words
// matching that pattern
bool search(TrieNode* root, string pattern)
{
int index;
TrieNode* pCrawl = root;
for (int level = 0; level < pattern.length(); level++)
{
index = int(pattern[level]) - 'A';
// Invalid pattern
if (!pCrawl->children[index])
return false;
pCrawl = pCrawl->children[index];
}
// print all words matching that pattern
printAllWords(pCrawl);
return true;
}
// Main function to print all words in the CamelCase
// dictionary that matches with a given pattern
void findAllWords(vector<string> dict, string pattern)
{
// construct Trie root node
TrieNode* root = getNewTrieNode();
// Construct Trie from given dict
for (string word : dict)
insert(root, word);
// search for pattern in Trie
if (!search(root, pattern))
cout << "No match found";
}
// Driver function
int main()
{
// dictionary of words where each word follows
// CamelCase notation
vector<string> dict = {
"Hi", "Hello", "HelloWorld", "HiTech", "HiGeek",
"HiTechWorld", "HiTechCity", "HiTechLab"
};
// pattern consisting of uppercase characters only
string pattern = "HT";
findAllWords(dict, pattern);
return 0;
}
Java
// Java program to print all words in the CamelCase
// dictionary that matches with a given pattern
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CamelCase {
// Alphabet size (# of upper-Case characters)
static final int ALPHABET_SIZE = 26;
// A Trie node
static class TrieNode {
TrieNode[] children = new TrieNode[ALPHABET_SIZE];
// isLeaf is true if the node represents
// end of a word
boolean isLeaf;
// vector to store list of complete words
// in leaf node
List<String> word;
public TrieNode() {
isLeaf = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
children[i] = null;
word = new ArrayList<String>();
}
}
static TrieNode root;
// Function to insert word into the Trie
static void insert(String word) {
int index;
TrieNode pCrawl = root;
for (int level = 0; level < word.length(); level++) {
// consider only uppercase characters
if (Character.isLowerCase(word.charAt(level)))
continue;
// get current character position
index = word.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;
// push word into vector associated with leaf node
(pCrawl.word).add(word);
}
// Function to print all children of Trie node root
static void printAllWords(TrieNode root) {
// if current node is leaf
if (root.isLeaf) {
for (String str : root.word)
System.out.println(str);
}
// recurse for all children of root node
for (int i = 0; i < ALPHABET_SIZE; i++) {
TrieNode child = root.children[i];
if (child != null)
printAllWords(child);
}
}
// search for pattern in Trie and print all words
// matching that pattern
static boolean search(String pattern) {
int index;
TrieNode pCrawl = root;
for (int level = 0; level < pattern.length(); level++) {
index = pattern.charAt(level) - 'A';
// Invalid pattern
if (pCrawl.children[index] == null)
return false;
pCrawl = pCrawl.children[index];
}
// print all words matching that pattern
printAllWords(pCrawl);
return true;
}
// Main function to print all words in the CamelCase
// dictionary that matches with a given pattern
static void findAllWords(List<String> dict, String pattern)
{
// construct Trie root node
root = new TrieNode();
// Construct Trie from given dict
for (String word : dict)
insert(word);
// search for pattern in Trie
if (!search(pattern))
System.out.println("No match found");
}
// Driver function
public static void main(String args[]) {
// dictionary of words where each word follows
// CamelCase notation
List<String> dict = Arrays.asList("Hi", "Hello",
"HelloWorld", "HiTech", "HiGeek",
"HiTechWorld", "HiTechCity",
"HiTechLab");
// pattern consisting of uppercase characters only
String pattern = "HT";
findAllWords(dict, pattern);
}
}
// This code is contributed by Sumit Ghosh
C#
// C# program to print all words in
// the CamelCase dictionary that
// matches with a given pattern
using System;
using System.Collections.Generic;
class GFG
{
// Alphabet size (# of upper-Case characters)
static int ALPHABET_SIZE = 26;
// A 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;
// vector to store list of complete words
// in leaf node
public List<String> word;
public TrieNode()
{
isLeaf = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
children[i] = null;
word = new List<String>();
}
}
static TrieNode root;
// Function to insert word into the Trie
static void insert(String word)
{
int index;
TrieNode pCrawl = root;
for (int level = 0;
level < word.Length; level++)
{
// consider only uppercase characters
if (char.IsLower(word[level]))
continue;
// get current character position
index = word[level] - 'A';
if (pCrawl.children[index] == null)
pCrawl.children[index] = new TrieNode();
pCrawl = pCrawl.children[index];
}
// mark last node as leaf
pCrawl.isLeaf = true;
// push word into vector
// associated with leaf node
(pCrawl.word).Add(word);
}
// Function to print all children
// of Trie node root
static void printAllWords(TrieNode root)
{
// if current node is leaf
if (root.isLeaf)
{
foreach (String str in root.word)
Console.WriteLine(str);
}
// recurse for all children of root node
for (int i = 0; i < ALPHABET_SIZE; i++)
{
TrieNode child = root.children[i];
if (child != null)
printAllWords(child);
}
}
// search for pattern in Trie and
// print all words matching that pattern
static bool search(String pattern)
{
int index;
TrieNode pCrawl = root;
for (int level = 0;
level < pattern.Length;
level++)
{
index = pattern[level] - 'A';
// Invalid pattern
if (pCrawl.children[index] == null)
return false;
pCrawl = pCrawl.children[index];
}
// print all words matching that pattern
printAllWords(pCrawl);
return true;
}
// Main function to print all words
// in the CamelCase dictionary that
// matches with a given pattern
static void findAllWords(List<String> dict,
String pattern)
{
// construct Trie root node
root = new TrieNode();
// Construct Trie from given dict
foreach (String word in dict)
insert(word);
// search for pattern in Trie
if (!search(pattern))
Console.WriteLine("No match found");
}
// Driver Code
public static void Main(String []args)
{
// dictionary of words where each word follows
// CamelCase notation
List<String> dict = new List<String>{"Hi", "Hello",
"HelloWorld", "HiTech",
"HiGeek", "HiTechWorld",
"HiTechCity", "HiTechLab"};
// pattern consisting of
// uppercase characters only
String pattern = "HT";
findAllWords(dict, pattern);
}
}
// This code is contributed by Princi Singh
Producción
HiTech HiTechCity HiTechLab HiTechWorld
Complejidad temporal : O(n*m) donde m es la longitud del patrón yn es la longitud del diccionario.
Espacio Auxiliar : O(n)
Este artículo es una contribución de Aditya Goel . 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