Dada una array de strings de M palabras y un diccionario de N palabras. La tarea es verificar si la string de palabras dada se puede formar a partir de palabras presentes en el diccionario.
Ejemplos:
dict[] = { find, a, geeks, all, for, on, geeks, answers, inter }
Input: str[] = { “buscar”, “todos”, “respuestas”, “on”, “geeks”, “para”, “geeks” };
Salida: SÍ ,
todas las palabras de str[] están presentes en el diccionario, por lo que la salida es SÍEntrada: str = {“buscar”, “a”, “geek”}
Salida: NO
En str[], “buscar” y “a” estaban presentes en el diccionario pero “geek” no está presente en el diccionario, por lo que la salida no es
Un enfoque ingenuo será hacer coincidir todas las palabras de la oración de entrada por separado con cada una de las palabras en el diccionario y mantener un recuento del número de ocurrencias de todas las palabras en el diccionario. Entonces, si el número de palabras en el diccionario es n y el número de palabras en la oración es m, este algoritmo tomará O (M * N) tiempo.
Un mejor enfoque será usar la versión modificada de la estructura de datos avanzada Trie , la complejidad del tiempo se puede reducir a O (M * t) donde t es la longitud de la palabra más larga en el diccionario que es menor que n. Así que aquí se ha realizado una modificación en el Node trie, de modo que la variable isEnd ahora es un número entero que almacena el recuento de ocurrencias de la palabra que termina en este Node. Además, la función de búsqueda se ha modificado para encontrar una palabra en el trie y, una vez encontrada, disminuir el recuento de isEnd de ese Node para que, para varias apariciones de una palabra en una oración, cada una coincida con una aparición separada de esa palabra en el diccionario. .
A continuación se muestra la ilustración del enfoque anterior:
C++
// C++ program to check if a sentence
// can be formed from a given set of words.
#include <bits/stdc++.h>
using namespace std;
const int ALPHABET_SIZE = 26;
// here isEnd is an integer that will store
// count of words ending at that node
struct trieNode {
trieNode* t[ALPHABET_SIZE];
int isEnd;
};
// utility function to create a new node
trieNode* getNode()
{
trieNode* temp = new (trieNode);
// Initialize new node with null
for (int i = 0; i < ALPHABET_SIZE; i++)
temp->t[i] = NULL;
temp->isEnd = 0;
return temp;
}
// Function to insert new words in trie
void insert(trieNode* root, string key)
{
trieNode* trail;
trail = root;
// Iterate for the length of a word
for (int i = 0; i < key.length(); i++) {
// If the next key does not contains the character
if (trail->t[key[i] - 'a'] == NULL) {
trieNode* temp;
temp = getNode();
trail->t[key[i] - 'a'] = temp;
}
trail = trail->t[key[i] - 'a'];
}
// isEnd is increment so not only the word but its count is also stored
(trail->isEnd)++;
}
// Search function to find a word of a sentence
bool search_mod(trieNode* root, string word)
{
trieNode* trail;
trail = root;
// Iterate for the complete length of the word
for (int i = 0; i < word.length(); i++) {
// If the character is not present then word
// is also not present
if (trail->t[word[i] - 'a'] == NULL)
return false;
// If present move to next character in Trie
trail = trail->t[word[i] - 'a'];
}
// If word foundthen decrement count of the word
if ((trail->isEnd) > 0 && trail != NULL) {
// if the word is found decrement isEnd showing one
// occurrence of this word is already taken so
(trail->isEnd)--;
return true;
}
else
return false;
}
// Function to check if string can be
// formed from the sentence
void checkPossibility(string sentence[], int m, trieNode* root)
{
int flag = 1;
// Iterate for all words in the string
for (int i = 0; i < m; i++) {
if (search_mod(root, sentence[i]) == false) {
// if a word is not found in a string then the
// sentence cannot be made from this dictionary of words
cout << "NO";
return;
}
}
// If possible
cout << "YES";
}
// Function to insert all the words of dictionary in the Trie
void insertToTrie(string dictionary[], int n,
trieNode* root)
{
for (int i = 0; i < n; i++)
insert(root, dictionary[i]);
}
// Driver Code
int main()
{
trieNode* root;
root = getNode();
// Dictionary of words
string dictionary[] = { "find", "a", "geeks",
"all", "for", "on",
"geeks", "answers", "inter" };
int N = sizeof(dictionary) / sizeof(dictionary[0]);
// Calling Function to insert words of dictionary to tree
insertToTrie(dictionary, N, root);
// String to be checked
string sentence[] = { "find", "all", "answers", "on",
"geeks", "for", "geeks" };
int M = sizeof(sentence) / sizeof(sentence[0]);
// Function call to check possibility
checkPossibility(sentence, M, root);
return 0;
}
Python3
# Python3 program to check if a sentence
# can be formed from a given set of words.
#include <bits/stdc++.h>
ALPHABET_SIZE = 26;
# here isEnd is an integer that will store
# count of words ending at that node
class trieNode:
def __init__(self):
self.t = [None for i in range(ALPHABET_SIZE)]
self.isEnd = 0
# utility function to create a new node
def getNode():
temp = trieNode()
return temp;
# Function to insert new words in trie
def insert(root, key):
trail = None
trail = root;
# Iterate for the length of a word
for i in range(len(key)):
# If the next key does not contains the character
if (trail.t[ord(key[i]) - ord('a')] == None):
temp = None
temp = getNode();
trail.t[ord(key[i]) - ord('a')] = temp;
trail = trail.t[ord(key[i]) - ord('a')];
# isEnd is increment so not only
# the word but its count is also stored
(trail.isEnd) += 1
# Search function to find a word of a sentence
def search_mod(root, word):
trail = root;
# Iterate for the complete length of the word
for i in range(len(word)):
# If the character is not present then word
# is also not present
if (trail.t[ord(word[i]) - ord('a')] == None):
return False;
# If present move to next character in Trie
trail = trail.t[ord(word[i]) - ord('a')];
# If word found then decrement count of the word
if ((trail.isEnd) > 0 and trail != None):
# if the word is found decrement isEnd showing one
# occurrence of this word is already taken so
(trail.isEnd) -= 1
return True;
else:
return False;
# Function to check if string can be
# formed from the sentence
def checkPossibility(sentence, m, root):
flag = 1;
# Iterate for all words in the string
for i in range(m):
if (search_mod(root, sentence[i]) == False):
# if a word is not found in a string then the
# sentence cannot be made from this dictionary of words
print('NO', end='')
return;
# If possible
print('YES')
# Function to insert all the words of dict in the Trie
def insertToTrie(dictionary, n, root):
for i in range(n):
insert(root, dictionary[i]);
# Driver Code
if __name__=='__main__':
root = getNode();
# Dictionary of words
dictionary = [ "find", "a", "geeks",
"all", "for", "on",
"geeks", "answers", "inter" ]
N = len(dictionary)
# Calling Function to insert words of dictionary to tree
insertToTrie(dictionary, N, root);
# String to be checked
sentence = [ "find", "all", "answers", "on",
"geeks", "for", "geeks" ]
M = len(sentence)
# Function call to check possibility
checkPossibility(sentence, M, root);
# This code is contributed by pratham76
Producción:
YES
Un enfoque eficiente será usar map. Mantenga el conteo de palabras en el mapa, itere en la string y verifique si la palabra está presente en el mapa. Si está presente, disminuya el recuento de la palabra en el mapa. Si no está presente, entonces no es posible hacer la string dada del diccionario de palabras dado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if a sentence
// can be formed from a given set of words.
#include <bits/stdc++.h>
using namespace std;
// Function to check if the word
// is in the dictionary or not
bool match_words(string dictionary[], string sentence[],
int n, int m)
{
// map to store all words in
// dictionary with their count
unordered_map<string, int> mp;
// adding all words in map
for (int i = 0; i < n; i++) {
mp[dictionary[i]]++;
}
// search in map for all
// words in the sentence
for (int i = 0; i < m; i++) {
if (mp[sentence[i]])
mp[sentence[i]] -= 1;
else
return false;
}
// all words of sentence are present
return true;
}
// Driver Code
int main()
{
string dictionary[] = { "find", "a", "geeks",
"all", "for", "on",
"geeks", "answers", "inter" };
int n = sizeof(dictionary) / sizeof(dictionary[0]);
string sentence[] = { "find", "all", "answers", "on",
"geeks", "for", "geeks" };
int m = sizeof(sentence) / sizeof(sentence[0]);
// Calling function to check if words are
// present in the dictionary or not
if (match_words(dictionary, sentence, n, m))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java program to check if a sentence
// can be formed from a given set of words.
import java.util.*;
class GFG
{
// Function to check if the word
// is in the dictionary or not
static boolean match_words(String dictionary[], String sentence[],
int n, int m)
{
// map to store all words in
// dictionary with their count
Map<String,Integer> mp = new HashMap<>();
// adding all words in map
for (int i = 0; i < n; i++)
{
if(mp.containsKey(dictionary[i]))
{
mp.put(dictionary[i], mp.get(dictionary[i])+1);
}
else
{
mp.put(dictionary[i], 1);
}
}
// search in map for all
// words in the sentence
for (int i = 0; i < m; i++)
{
if (mp.containsKey(sentence[i]))
mp.put(sentence[i],mp.get(sentence[i])-1);
else
return false;
}
// all words of sentence are present
return true;
}
// Driver Code
public static void main(String[] args)
{
String dictionary[] = { "find", "a", "geeks",
"all", "for", "on",
"geeks", "answers", "inter" };
int n = dictionary.length;
String sentence[] = { "find", "all", "answers", "on",
"geeks", "for", "geeks" };
int m = sentence.length;
// Calling function to check if words are
// present in the dictionary or not
if (match_words(dictionary, sentence, n, m))
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to check if a sentence
# can be formed from a given set of words.
# Function to check if the word
# is in the dictionary or not
def match_words(dictionary, sentence, n, m):
# map to store all words in
# dictionary with their count
mp = dict()
# adding all words in map
for i in range(n):
mp[dictionary[i]] = mp.get(dictionary[i], 0) + 1
# search in map for all
# words in the sentence
for i in range(m):
if (mp[sentence[i]]):
mp[sentence[i]] -= 1
else:
return False
# all words of sentence are present
return True
# Driver Code
dictionary = ["find", "a", "geeks", "all", "for",
"on", "geeks", "answers", "inter"]
n = len(dictionary)
sentence = ["find", "all", "answers", "on",
"geeks", "for", "geeks"]
m = len(sentence)
# Calling function to check if words are
# present in the dictionary or not
if (match_words(dictionary, sentence, n, m)):
print("YES")
else:
print("NO")
# This code is contributed by mohit kumar
C#
// C# program to check if a sentence
// can be formed from a given set of words.
using System;
using System.Collections.Generic;
class GFG
{
// Function to check if the word
// is in the dictionary or not
static Boolean match_words(String []dictionary,
String []sentence,
int n, int m)
{
// map to store all words in
// dictionary with their count
Dictionary<String,
int> mp = new Dictionary<String,
int>();
// adding all words in map
for (int i = 0; i < n; i++)
{
if(mp.ContainsKey(dictionary[i]))
{
mp[dictionary[i]] = mp[dictionary[i]] + 1;
}
else
{
mp.Add(dictionary[i], 1);
}
}
// search in map for all
// words in the sentence
for (int i = 0; i < m; i++)
{
if (mp.ContainsKey(sentence[i]) && mp[sentence[i]] > 0)
mp[sentence[i]] = mp[sentence[i]] - 1;
else
return false;
}
// all words of sentence are present
return true;
}
// Driver Code
public static void Main(String[] args)
{
String []dictionary = { "find", "a", "geeks",
"all", "for", "on",
"geeks", "answers", "inter" };
int n = dictionary.Length;
String []sentence = { "find", "all", "answers", "on",
"geeks", "for", "geeks", "geeks" };
int m = sentence.Length;
// Calling function to check if words are
// present in the dictionary or not
if (match_words(dictionary, sentence, n, m))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to check if a sentence
// can be formed from a given set of words.
// Function to check if the word
// is in the dictionary or not
function match_words(dictionary, sentence, n, m)
{
// map to store all words in
// dictionary with their count
let mp = new Map();
// Adding all words in map
for(let i = 0; i < n; i++)
{
if(mp.has(dictionary[i]))
{
mp.set(dictionary[i],
mp.get(dictionary[i]) + 1);
}
else
{
mp.set(dictionary[i], 1);
}
}
// Search in map for all
// words in the sentence
for(let i = 0; i < m; i++)
{
if (mp.has(sentence[i]))
mp.set(sentence[i],
mp.get(sentence[i]) - 1);
else
return false;
}
// All words of sentence are present
return true;
}
// Driver code
let dictionary = [ "find", "a", "geeks",
"all", "for", "on",
"geeks", "answers", "inter" ];
let n = dictionary.length;
let sentence = [ "find", "all", "answers", "on",
"geeks", "for", "geeks" ];
let m = sentence.length;
// Calling function to check if words are
// present in the dictionary or not
if (match_words(dictionary, sentence, n, m))
document.write("YES");
else
document.write("NO");
// This code is contributed by patel2127
</script>
Producción:
YES
Complejidad de tiempo: O(M)
Complejidad de espacio : O(N) donde N es ninguna de las palabras en un diccionario