Dado un diccionario, averigüe si la palabra dada puede estar formada por dos palabras en el diccionario.
Nota: Las palabras en el diccionario deben ser únicas y la palabra a formar no debe ser una repetición de las mismas palabras que están presentes en el Trie.
Ejemplos:
Input : dictionary[] = {"news", "abcd", "tree",
"geeks", "paper"}
word = "newspaper"
Output : Yes
We can form "newspaper" using "news" and "paper"
Input : dictionary[] = {"geeks", "code", "xyz",
"forgeeks", "paper"}
word = "geeksforgeeks"
Output : Yes
Input : dictionary[] = {"geek", "code", "xyz",
"forgeeks", "paper"}
word = "geeksforgeeks"
Output : No
La idea es almacenar todas las palabras del diccionario en un Trie . Hacemos búsqueda de prefijos para la palabra dada. Una vez que encontramos un prefijo, buscamos el resto de la palabra.
Algoritmo:
1- Store all the words of the dictionary in a Trie. 2- Start searching for the given word in Trie. If it partially matched then split it into two parts and then search for the second part in the Trie. 3- If both found, then return true. 4- Otherwise return false.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to check if a string can be
// formed by concatenating two words
#include<bits/stdc++.h>
using namespace std;
// Converts key current character into index
// use only 'a' through 'z'
#define char_int(c) ((int)c - (int)'a')
// Alphabet size
#define SIZE (26)
// Trie Node
struct TrieNode
{
TrieNode *children[SIZE];
// isLeaf is true if the node represents
// end of a word
bool isLeaf;
};
// Returns new trie node (initialized to NULLs)
TrieNode *getNode()
{
TrieNode * newNode = new TrieNode;
newNode->isLeaf = false;
for (int i =0 ; i< SIZE ; i++)
newNode->children[i] = NULL;
return newNode;
}
// If not present, inserts key into Trie
// If the key is prefix of trie node, just
// mark leaf node
void insert(TrieNode *root, string Key)
{
int n = Key.length();
TrieNode * pCrawl = root;
for (int i=0; i<n; i++)
{
int index = char_int(Key[i]);
if (pCrawl->children[index] == NULL)
pCrawl->children[index] = getNode();
pCrawl = pCrawl->children[index];
}
// make last node as leaf node
pCrawl->isLeaf = true;
}
// Searches a prefix of key. If prefix is present,
// returns its ending position in string. Else
// returns -1.
int findPrefix(struct TrieNode *root, string key)
{
int pos = -1, level;
struct TrieNode *pCrawl = root;
for (level = 0; level < key.length(); level++)
{
int index = char_int(key[level]);
if (pCrawl->isLeaf == true)
pos = level;
if (!pCrawl->children[index])
return pos;
pCrawl = pCrawl->children[index];
}
if (pCrawl != NULL && pCrawl->isLeaf)
return level;
}
// Function to check if word formation is possible
// or not
bool isPossible(struct TrieNode* root, string word)
{
// Search for the word in the trie and
// store its position upto which it is matched
int len = findPrefix(root, word);
// print not possible if len = -1 i.e. not
// matched in trie
if (len == -1)
return false;
// If word is partially matched in the dictionary
// as another word
// search for the word made after splitting
// the given word up to the length it is
// already,matched
string split_word(word, len, word.length()-(len));
int split_len = findPrefix(root, split_word);
// check if word formation is possible or not
return (len + split_len == word.length());
}
// Driver program to test above function
int main()
{
// Let the given dictionary be following
vector<string> dictionary = {"geeks", "forgeeks",
"quiz", "geek"};
string word = "geeksquiz"; //word to be formed
// root Node of trie
TrieNode *root = getNode();
// insert all words of dictionary into trie
for (int i=0; i<dictionary.size(); i++)
insert(root, dictionary[i]);
isPossible(root, word) ? cout << "Yes":
cout << "No";
return 0;
}
Java
import java.util.ArrayList;
import java.util.List;
// Java program to check if a string can be
// formed by concatenating two words
public class GFG {
// Alphabet size
final static int SIZE = 26;
// Trie Node
static class TrieNode
{
TrieNode[] children = new TrieNode[SIZE];
// isLeaf is true if the node represents
// end of a word
boolean isLeaf;
// constructor
public TrieNode() {
isLeaf = false;
for (int i =0 ; i< SIZE ; i++)
children[i] = null;
}
}
static TrieNode root;
// If not present, inserts key into Trie
// If the key is prefix of trie node, just
// mark leaf node
static void insert(TrieNode root, String Key)
{
int n = Key.length();
TrieNode pCrawl = root;
for (int i=0; i<n; i++)
{
int index = Key.charAt(i) - 'a';
if (pCrawl.children[index] == null)
pCrawl.children[index] = new TrieNode();
pCrawl = pCrawl.children[index];
}
// make last node as leaf node
pCrawl.isLeaf = true;
}
// Searches a prefix of key. If prefix is present,
// returns its ending position in string. Else
// returns -1.
static List<Integer> findPrefix(TrieNode root, String key)
{
List<Integer> prefixPositions = new ArrayList<Integer>();
int level;
TrieNode pCrawl = root;
for (level = 0; level < key.length(); level++)
{
int index = key.charAt(level) - 'a';
if (pCrawl.isLeaf == true)
prefixPositions.add(level);
if (pCrawl.children[index] == null)
return prefixPositions;
pCrawl = pCrawl.children[index];
}
if (pCrawl != null && pCrawl.isLeaf)
prefixPositions.add(level);
return prefixPositions;
}
// Function to check if word formation is possible
// or not
static boolean isPossible(TrieNode root, String word)
{
// Search for the word in the trie and get its prefix positions
// upto which there is matched
List<Integer> prefixPositions1 = findPrefix(root, word);
// Word formation is not possible if the word did not have
// at least one prefix match
if (prefixPositions1.isEmpty())
return false;
// Search for rest of substring for each prefix match
for (Integer len1 : prefixPositions1) {
String restOfSubstring = word.substring(len1, word.length());
List<Integer> prefixPositions2 = findPrefix(root, restOfSubstring);
for (Integer len2 : prefixPositions2) {
// check if word formation is possible
if (len1 + len2 == word.length())
return true;
}
}
return false;
}
// Driver program to test above function
public static void main(String args[])
{
// Let the given dictionary be following
String[] dictionary = {"news", "newspa", "paper", "geek"};
String word = "newspaper"; //word to be formed
// root Node of trie
root = new TrieNode();
// insert all words of dictionary into trie
for (int i=0; i<dictionary.length; i++)
insert(root, dictionary[i]);
if(isPossible(root, word))
System.out.println( "Yes");
else
System.out.println("No");
}
}
// This code is contributed by Sumit Ghosh
// Updated by Narendra Jha
C#
// C# program to check if a string can be
// formed by concatenating two words
using System;
using System.Collections.Generic;
class GFG
{
// Alphabet size
readonly public static int SIZE = 26;
// Trie Node
public class TrieNode
{
public TrieNode []children = new TrieNode[SIZE];
// isLeaf is true if the node
// represents end of a word
public bool isLeaf;
// constructor
public TrieNode()
{
isLeaf = false;
for (int i = 0 ; i < SIZE ; i++)
children[i] = null;
}
}
static TrieNode root;
// If not present, inserts key into Trie
// If the key is prefix of trie node, just
// mark leaf node
static void insert(TrieNode root, String Key)
{
int n = Key.Length;
TrieNode pCrawl = root;
for (int i = 0; i < n; i++)
{
int index = Key[i] - 'a';
if (pCrawl.children[index] == null)
pCrawl.children[index] = new TrieNode();
pCrawl = pCrawl.children[index];
}
// make last node as leaf node
pCrawl.isLeaf = true;
}
// Searches a prefix of key. If prefix
// is present, returns its ending position
// in string. Else returns -1.
static List<int> findPrefix(TrieNode root, String key)
{
List<int> prefixPositions = new List<int>();
int level;
TrieNode pCrawl = root;
for (level = 0; level < key.Length; level++)
{
int index = key[level] - 'a';
if (pCrawl.isLeaf == true)
prefixPositions.Add(level);
if (pCrawl.children[index] == null)
return prefixPositions;
pCrawl = pCrawl.children[index];
}
if (pCrawl != null && pCrawl.isLeaf)
prefixPositions.Add(level);
return prefixPositions;
}
// Function to check if word
// formation is possible or not
static bool isPossible(TrieNode root, String word)
{
// Search for the word in the trie
// and get its prefix positions
// upto which there is matched
List<int> prefixPositions1 = findPrefix(root, word);
// Word formation is not possible
// if the word did not have
// at least one prefix match
if (prefixPositions1.Count==0)
return false;
// Search for rest of substring
// for each prefix match
foreach (int len1 in prefixPositions1)
{
String restOfSubstring = word.Substring(len1,
word.Length-len1);
List<int> prefixPositions2 = findPrefix(root,
restOfSubstring);
foreach (int len2 in prefixPositions2)
{
// check if word formation is possible
if (len1 + len2 == word.Length)
return true;
}
}
return false;
}
// Driver code
public static void Main(String []args)
{
// Let the given dictionary be following
String[] dictionary = {"news", "newspa", "paper", "geek"};
// word to be formed
String word = "newspaper";
// root Node of trie
root = new TrieNode();
// insert all words of dictionary into trie
for (int i = 0; i < dictionary.Length; i++)
insert(root, dictionary[i]);
if(isPossible(root, word))
Console.WriteLine( "Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to check if a string
// can be formed by concatenating two words
// Alphabet size
let SIZE = 26;
// Trie Node
class TrieNode
{
constructor()
{
this.isLeaf = false;
this.children = new Array(SIZE);
for(let i = 0 ; i < SIZE; i++)
this.children[i] = null;
}
}
let root;
// If not present, inserts key into Trie
// If the key is prefix of trie node, just
// mark leaf node
function insert(root, Key)
{
let n = Key.length;
let pCrawl = root;
for(let i = 0; i < n; i++)
{
let index = Key[i].charCodeAt(0) -
'a'.charCodeAt(0);
if (pCrawl.children[index] == null)
pCrawl.children[index] = new TrieNode();
pCrawl = pCrawl.children[index];
}
// Make last node as leaf node
pCrawl.isLeaf = true;
}
// Searches a prefix of key. If prefix
// is present, returns its ending
// position in string. Else returns -1.
function findPrefix(root, key)
{
let prefixPositions = [];
let level;
let pCrawl = root;
for(level = 0; level < key.length; level++)
{
let index = key[level].charCodeAt(0) -
'a'.charCodeAt(0);
if (pCrawl.isLeaf == true)
prefixPositions.push(level);
if (pCrawl.children[index] == null)
return prefixPositions;
pCrawl = pCrawl.children[index];
}
if (pCrawl != null && pCrawl.isLeaf)
prefixPositions.push(level);
return prefixPositions;
}
// Function to check if word formation
// is possible or not
function isPossible(root, word)
{
// Search for the word in the trie and
// get its prefix positions upto which
// there is matched
let prefixPositions1 = findPrefix(root, word);
// Word formation is not possible if
// the word did not have at least one
// prefix match
if (prefixPositions1.length == 0)
return false;
// Search for rest of substring for
// each prefix match
for(let len1 = 0;
len1 < prefixPositions1.length;
len1++)
{
let restOfSubstring = word.substring(
prefixPositions1[len1], word.length);
let prefixPositions2 = findPrefix(
root, restOfSubstring);
for(let len2 = 0;
len2 < prefixPositions2.length;
len2++)
{
// Check if word formation is possible
if (prefixPositions1[len1] +
prefixPositions2[len2] == word.length)
return true;
}
}
return false;
}
// Driver code
let dictionary = [ "news", "newspa",
"paper", "geek" ];
// word to be formed
let word = "newspaper";
// Root Node of trie
root = new TrieNode();
// Insert all words of dictionary into trie
for(let i = 0; i < dictionary.length; i++)
insert(root, dictionary[i]);
if (isPossible(root, word))
document.write("Yes");
else
document.write("No");
// This code is contributed by rag2127
</script>
Producción:
Yes
Ejercicio:
una versión generalizada del problema consiste en verificar si una palabra determinada se puede formar mediante la concatenación de 1 o más palabras del diccionario. Escriba el código para la versión generalizada.
Este artículo es una contribución de Sahil Chhabra (akku) . 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.
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